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

Drawing out the universe of NP problems

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.

  1. 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)
  2. 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.
  3. 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.
step 2 of the formula
  • 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.

the most popular NPC problems per each category

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).

Full-time cat & dog lover, part time developer 💖 I like writing to help others! @helenzhxng | Previously @Paypal & @NASA , now @Squarespace—

Full-time cat & dog lover, part time developer 💖 I like writing to help others! @helenzhxng | Previously @Paypal & @NASA , now @Squarespace—