Polynomial Time Reductions23 Dec 2017
Abstract: this post gives a quick overview of polynomial time reductions – a method for computationally cheap transformations of problems into different problems. Chiefly, it’s used to prove that some problems are at least as hard as the other ones, which taps into the discussion of P vs NP problem.
Simple problems and hard problems
Let’s divide all computational problems into two sets: the simple problems and the hard ones. The simple problems are those for which there exists (at least hypothetically) an algorithm that solves them in time polynomial from the size of the input. The hard problems are those for which there does not (and cannot) exist such an algorithm.
An example of a simple problem is the following:
You are given a sequence of numbers. Is the sequence increasing?
One algorithm for this problem is to go along the sequence and compare neighboring numbers. If in all comparisons the number to the left is smaller than the number to the right, then the sequence is indeed increasing. In total, there are comparisons.
An example of a hard problem is the following:
You are given a program. Does it halt within steps?
encoded in binary uses bits, yet a trivial simulation of the program takes steps. This means that for an input of length the simulation will take steps and that this problem can only be solved in exponential time.
The clique problem
Now, suppose we have the following problem:
Does there exist a clique (a set of vertices in a graph such that its every vertex is connected to its every other vertex) of size in a given graph?
We’ll call this problem and we want to know if it’s simple or hard, i.e. we need to prove that is either simple or hard.
If is simple, then, by definition of a simple problem, there exists a polynomial time algorithm for it. And by finding such an algorithm we would prove that is simple.
But if is hard, then to prove this fact we would have to prove that there cannot possibly exist a polynomial time algorithm, which is intuitively a much more difficult task.
Polynomial time reductions
There exists a walkaround for the second case, though.
Let us have a problem that we already know is hard. We’ll call it . Suppose, we found a way to “reduce” to and the reduction takes polynomial time.
Then, if is simple, can be solved by first transforming it into and then solving . The first step takes polynomial time (because the transformation is polynomial time) and the second step takes polynomial time (by definition of a simple problem), thus the entire solution of takes polynomial time. But this contradicts the fact that is hard! It follows that is not in fact simple.
So, to reduce to means “to solve the problem through the problem ”. It’s absurdly easy to confuse which way the reductions work and to try to reduce to when you need to reduce to . This happens because the terminology is dumb as shit. In everyday life we reduce something big to something small; here, it’s the opposite. The way to intuitively remember it is to keep in mind that a simple problem can be solved through a hard problem–doing it would simply be inefficient. But a hard problem cannot be solved through an easy problem–because this would imply that that problem is not hard after all. Thus, we always reduce a simpler problem to a more difficult one.
Let us return to now. Again, the problem statement is:
Does there exist a clique (a set of vertices in a graph that are all connected between each other) of size in a given graph?
And we suspect that this is indeed a hard problem. In this case, we have to find some problem that we know for sure is hard, and then reduce it to . A hard problem we will use here is 3-SAT problem, the formulation of which is the following:
Given a boolean expression that
(1) consists of clauses joined by ANDs
(2) each clause consists of exactly 3 variables (or their negations), joined by ORs
(for example: )
are there such values that the expression is TRUE?
To prove that is hard we need to reduce 3-SAT to . The reduction is elegant but it’s not super straightforward. Moreover it’s explained clearly and beautifully over here, so I invite to check it out and will omit the reduction in this post.
Now, there’s several things to clear up here.
First, I lied when I wrote that we know that 3-SAT is hard. 3-SAT belongs to a large class of problems all of which can be polynomially reduced to one another. This class is called NP-complete (NPC). NPC consists of the hardest problems that can be verified in polynomial time. However, we don’t know whether there exists an algorithm that solves NPC problems in polynomial time. In fact, if we call simple problems P, then finding out whether NPC P would solve the question whether P=NP.
So, for example, while we can reduce the problem of ordering numbers to e.g. clique problem, we don’t know if a reduction from clique to ordering exists. Finding such a reduction or proving that it doesn’t exist would actually constitute the solution of P versus NP.
Ok, one last time: if we suspect that is at least as hard as , then we reduce to to prove it.
A bit more about P, NP, etc.
I find most of the descriptions of the terms P, NP, NPC, and NP-hard to be far from clear. Even the best stackoverflow answer is not as clear as it could possibly be. The way I understand it is that there’s a very natural hierarchy:
- P – the problems that can be solved in polynomial time.
- NP – the problems answer to which is “yes” or “no”, and if we are presented with a solution that answers “yes”, this solution can be verified in polynomial time (for example, if we’re given a solution for that claims to find a clique of size , we will need to verify that each vertex is connected to other vertices in the clique, for a total of steps.
- NPC – the hardest problems in NP. Alternatively, the problems to which we can reduce all problems in NP.
- NP-hard – the problems that are at least as hard as NPC.
So, if PNP, then P=NP=NPC. If P NP, then P NP and NP NPC.
OpenDSA, Limits to Computing. A more in-depth look a the topic with several reductions presented (the same site I linked to for 3-SAT reduction).
Introduction to the Theory of Computation by Michael Sipser. My fav computation theory textbook.
Thanks to Sergei Obiedkov for reading early drafts of this post and helping me to wrap my head around all of this stuff.
Feel free to share your thoughts on this post with me!