Now that we’ve gone through a very basic introduction to computational complexity, we’re ready
to take a high-level glimpse at some of the more interesting things that arise from it. The one
that you’ll hear about most often is “P vs NP”, which is what I’m going to write about today.
So, what are P and NP?
P and NP are two very broad classes of computational problems. When we’re talking about P and NP, we’re talking about the intrinsic complexity of a problem – that is, a minimum complexity bound on the growth rate of the worst case performance of any algorithm that solves the problem.
P is the class of problems that can be solved in polynomial time on a deterministic effective
computing system (ECS). Loosely speaking, all computing machines that exist in the real world are
deterministic ECSs. So P is the class of things that can be computed in polynomial time on real computers.
NP is the class of problems that can be solved in polynomial time on non-deterministic
ECSs. A non-deterministic machine is a machine which can execute programs in a way where whenever there are multiple choices, rather than iterate through them one at a time, it can follow all choices/all paths at the same time, and the computation will succeed if any of those
paths succeed; if multiple paths lead to success, one of them will be selected by some unspecified mechanism; we usually say that they’ll pick the first path to lead to a successful result.
The idea of non-determinism in effective/Turing-equivalent computing systems is a tough
thing to grasp. There are two ways of thinking about it that help most people understand what it
means: there’s the low-level explanation, and the high level explanation.
The low level explanation is based on the basic concept of the Turing machine. (If you need
a reminder of how a Turing machine works, I wrote an explanation here.) In a Turing machine, you’ve got a tape full of data cells, with a head that can read and/or write data on
the cell under it, and you’ve got a state. Each step of the computation, you can look at the contents of the tape cell under the head, and then using the data on that cell and the current state of the machine, and use those to decide what (if anything) to write onto the current tape cell; what state to adopt, and what direction to move the head on the tape. In a deterministic Turing machine, for a given pair (cell,state) of tape cell data and machine state, there can be only one possible (write,state,move) action for the machine. In a non-deterministic machine, there can be multiple actions for a given (cell,state) pair. When there are multiple choices, the machine picks all of them; you can think of it as the machine splitting itself into multiple copies, each of which picks one of the choices; and whichever copy succeeds first becomes the result of the
The high level explanation is a simpler idea, and it’s closer to what we use in practice for
specifying when some problem is in NP, but it sounds pretty weird. A problem whose solution can
be computed in polynomial time on a non-deterministic machine is equivalent to a problem where
a proposed solution can be verified correct in polynomial time on a deterministic machine. You can
specify a non-deterministic machine that guesses all possible solution, following all of those paths at once, and returning a result whenever it finds a solution that it can verify is correct. So if you
can check a solution deterministically in polynomial time (not produce a solution, but just verify that the solution is correct), then it’s in NP.
The distinction can become much clearer with an example. There’s a classic problem called the
subset/sum problem (SS). In the SS problem, you’re given an arbitrary set of integers. The question is,
can you find any non-empty subset of values in the set whose sum is 0? It should be pretty obvious that
checking a solution is in P: a solution is a list of integers whose maximum length is the size
of the entire set; to check a potential solution, sum the values in the solution, and see if the result
is 0. That’s O(n) where n is the number of values in the set. But finding a solution is
hard. The solution could be any subset of any size larger than 0; for a set of n elements,
that’s 2n-1 possible subsets. Even if you use clever tricks to reduce the number of possible
solutions, you’re still well into exponential territory in the worse case. So you can non-deterministically guess a solution and test it in linear time; but no one has found any way
of producing a correct solution deterministically in less than O(2n) steps.
One of the great unsolved problems in theoretical computer science is: does P = NP? That is, is
the set of problems that can be solved in polynomial time on a non-deterministic machine the same as the set of problems that can be solved in polynomial time on a deterministic machine? We know for certain that P ⊆ NP – that is, that all problems that can be solved in polynomial time on a deterministic machine can also be solved in polynomial time on a non-deterministic machine. We simple do not know.
For computing devices simpler than Turing-equivalent, we know the relationships between the deterministic and non-deterministic problem families. For example, for finite state machines,
non-deterministic FSMs are no faster or more capable than deterministic ones (So DFA = NFA); for pushdown automata, the deterministic versions are strictly weaker than the non-deterministic ones (D-PDA ⊂ N-PDA). But what about Turing machines, or any other Turing-equivalent ECS? Not a clue. I know people who study computational complexity who think that P=NP, and that we will find a polynomial time deterministic solution to an NP problem any year now. Personally, I suspect that P ≠ NP,
based on intuition from the PDA case; as computing devices get more complex, we start to see more
differences between the deterministic and non-deterministic machines, and I personally think that that
will hold true all the way up to full ECS’s. But I have no proof to back that up, just intuition.
Within NP, there are a set of particularly interesting problems which are called NP-complete. An NP-complete problem is one where we can prove that if there is a
P-time computation that solved that problem, it would mean that there was a P-time solution
for every problem in NP, and thus that P=NP. We’ve identified hundreds (thousands?) of
NP-complete problems, but no one has ever found a P-time solution for any of them.
So how do we show that something is NP complete? It sounds like a very difficult thing to do. And doing it from first principles is extremely difficult. Fortunately, once it’s been done for one problem, we can piggyback on that solution. The way to prove NP-completeness is based on
the idea of problem reduction. If we have two problems S and T, and we can show that
any instance of S can be transformed into an instance of T in polynomial time, then we say that S is polynomial-time reducible to T. If T is NP-complete, then every problem in NP is polynomial-time reducible to T.
The trick is: once we know a problem T which is NP complete, then for any other problem U, if we can show that T is polynomial-time reducible to U, then U must be NP-complete as well. If we can reduce T to U, but we don’t know how to reduce U to T, then we don’t just say that U is NP-complete; we say that it’s NP-hard. Many people think that if we could show whether or not NP=NP-Hard, then we’d also know whether P=NP; others disagree.
Anyway, there are a lot of problems which have been proven NP-complete. So given a new problem,
there are a lot of different NP-complete problems that you can use as a springboard for proving that
your new problem is also NP complete.
If you trace back, you’ll find that most NP-completeness proofs are ultimately built on top of NP-completeness proof of one fundamental problem, whose nature makes it particularly appropriate as
a universal reduction target – and it’s also the first problem that was proven to be NP-complete. It’s called the propositional satisfaction problem (aka SAT), which was shown to be NP-complete via a rather difficult poof. For any other problem, if we can show that we can translate any instance of a SAT problem to an instance of some other problem in polynomial time, then that other problem must also be NP-complete. And SAT (or one of its simpler variations, 3-SAT) is particularly easy to work with, and show how to translate instances of SAT to instances of other problems.
The SAT problem is a neat one. Take a set of boolean variables of size n,
b1,…,bn, and their complements, not(b1),…,not(bn);
these are called atoms. Now, form an arbitrary logical statement using atoms joined by logical ANDs and ORs. The problem is, can you find an assignment of the boolean variables to true and
false so that the statement is true (satisfied).
The only problem with SAT is that it’s so general. The set of all logical equations consisting of
an arbitrary set of atoms joined together in any syntactically valid form – it’s an enormous set; but worse, it’s got a huge amount of structural variation. To work with it, and show a P-time reduction from SAT to some other problem, and be absolutely sure that you’ve covered every possible case – that’s a tough job. Too tough; it’s awfully easy to miss just one little case; and missing one case can
give you an apparent reduction that shows P=NP.
What we typically do, then, is used a constrained version of SAT. Any arbitrary SAT equation can be
P-time transformed into a equivalent equation in a particular form consisting of groups of 3 atoms
(triples), where the members of a triple are joined by logical “OR”s, and triples are joined by logical
“AND”s. Solving the SAT problem for equations in the constrained triple form is called 3-SAT. 3-SAT is NP-complete, just like the general SAT problem; and because it is so constrained, 3-SAT is a much easier basis for constructing reduction-based NP-completeness proofs.