# TL;DR Proving NP-Completeness

## A simple, fool-proof outline for reducing problems to NPC (for anyone who needs a refresher or accidentally missed lecture)

**Useful Definitions: ****P: **problems that can be solved in polynomial time **NP:** non-deterministic polynomial, i.e. for any NP problem — if we are given a possible solution we can verify if it is valid or not in polynomial time **NP-Complete: **subset of NP problems where there is *no known efficient method** *to find the solution

## Getting Started

In general, it’s easier to understand a concept when you know the ** why** behind it. So what is the

**we need to remember when doing NPC proofs?**

*why***Our goal: **To show that our problem is just as difficult as a known NPC problem, or alternatively to show that all instances of a known NPC problem can be reduced to our problem. **Why does it matter?** If we know our problem is just as hard as a known NPC problem, then we know that there is no efficient way of finding the solution.

**The Formula**

- Show that your problem belongs in the world of NP problems (i.e. given a specific instance of the problem with a possible solution, show that in polynomial time you can verify if the solution is correct)
- Next, establish a relationship between a known NP-Complete problem and your problem — more specifically, show how every instance of the NPC problem can be reduced to your current problem with some polynomial time / work.
- Lastly, assert an ‘if and only if’ such that a solution for your current problem exists
there is a solution for the NPC problem.*if and only if*

**General Categories of NPC Problems**

**Packing Problems***— Given a collection of things and some rules about how these items can be picked, find a way to**choose at least k**things from the collection that satisfy your goal.**Covering Problems***— Given a collection of things and a certain goal, find a way to**pick at most k things**such that you can meet your goal.**Partitioning Problems**— A combination between a packing and a covering problem, i.e. given a collection of things, find a way you can pick subsets such that they do not overlap (are disjoint) and can completely cover the original collection.**Sequencing Problems**— When you have to consider all possible permutations of a given collection in order to find a solution and the order (or sequence) matters.

**Packing & covering problems tend to apply to most basic NPC proofs, out of all four categories these two are probably the most handy to know.*

# In a nutshell the easiest way to prove a problem is NPC is to identify which category seems most applicable to it, and then make the reduction to your problem.

I hope this can help some of you out there! (I’m talking to you fellow BU CS330 takers, or anyone who’s going through chapter 8 of **Algorithm Design **by Jon Kleinberg & Eva Tardos).