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 why we need to remember when doing NPC proofs?
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 if and only if there is a solution for the NPC problem.
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).
