Now that we’ve gone through a very basic introduction to computational complexity, we’re ready
\nto take a high-level glimpse at some of the more interesting things that arise from it. The one
\nthat you’ll hear about most often is “P vs NP”, which is what I’m going to write about today.<\/p>\n
<\/p>\n
So, what are P and NP? <\/p>\n
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<\/em> – that is, a minimum complexity bound on the growth rate of the worst case performance of any<\/em> algorithm that solves the problem.<\/p>\n P is the class of problems that can be solved in polynomial time on a deterministic effective NP is the class of problems that can be solved in polynomial time on non-deterministic<\/em> The idea of non-determinism in effective\/Turing-equivalent computing systems is a tough The low level explanation is based on the basic concept of the Turing machine. (If you need The high level explanation is a simpler idea, and it’s closer to what we use in practice for The distinction can become much clearer with an example. There’s a classic problem called the One of the great unsolved problems in theoretical computer science is: does P = NP? That is, is 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, Within NP, there are a set of particularly interesting problems which are called NP-complete<\/em>. An NP-complete problem is one where we can prove that if there is a The SS problem mentioned above is NP-complete. So are a lot of other interesting problems: 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<\/em> 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 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.<\/p>\n Anyway, there are a lot of problems which have been proven NP-complete. So given a new problem,
\ncomputing system (ECS). Loosely speaking, all computing machines that exist in the real world are
\ndeterministic ECSs. So P is the class of things that can be computed in polynomial time on real computers.<\/p>\n
\nECSs. 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<\/em> at the same time, and the computation will succeed if any<\/em> of those
\npaths 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.<\/p>\n
\nthing to grasp. There are two ways of thinking about it that help most people understand what it
\nmeans: there’s the low-level explanation, and the high level explanation.<\/p>\n
\na reminder of how a Turing machine works, I wrote an explanation here<\/a>.) In a Turing machine, you’ve got a tape full of data cells, with a head that can read and\/or write data on
\nthe cell under it, and you’ve got a state<\/em>. 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<\/em> actions for a given (cell,state) pair. When there are multiple choices, the machine picks all of them<\/em>; 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
\ncomputation.<\/p>\n
\nspecifying when some problem is in NP, but it sounds pretty weird. A problem whose solution can
\nbe computed in polynomial time on a non-deterministic machine is equivalent to a problem where
\na proposed solution can be verified correct in polynomial time on a deterministic machine. You can
\nspecify 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
\ncan check a solution deterministically in polynomial time (not produce a solution, but just verify that the solution is correct), then it’s in NP.<\/p>\n
\nsubset\/sum problem (SS). In the SS problem, you’re given an arbitrary set of integers. The question is,
\ncan you find any non-empty subset of values in the set whose sum is 0? It should be pretty obvious that
\nchecking<\/em> a solution is in P: a solution is a list of integers whose maximum length is the size
\nof the entire set; to check a potential solution, sum the values in the solution, and see if the result
\nis 0. That’s O<\/b>(n) where n is the number of values in the set. But finding<\/em> a solution is
\nhard. The solution could be any<\/em> subset of any size larger than 0; for a set of n elements,
\nthat’s 2n<\/sup>-1 possible subsets. Even if you use clever tricks to reduce the number of possible
\nsolutions, 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
\nof producing a correct solution deterministically in less than O<\/b>(2n<\/sup>) steps.<\/p>\n
\nthe set of problems that can<\/em> 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.<\/p>\n
\nnon-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,
\nbased on intuition from the PDA case; as computing devices get more complex, we start to see more
\ndifferences between the deterministic and non-deterministic machines, and I personally think that that
\nwill hold true all the way up to full ECS’s. But I have no proof to back that up, just intuition.<\/p>\n
\nP-time computation that solved that problem, it would mean that there was a P-time solution
\nfor every<\/em> problem in NP, and thus that P=NP. We’ve identified hundreds (thousands?) of
\nNP-complete problems, but no one has ever found a P-time solution for any of them.<\/p>\n
\ngraph coloring<\/a>, the traveling salesman<\/a>, clique detection in graphs<\/a>, and many more.<\/p>\n
\nthe idea of problem reduction<\/em>. If we have two problems S and T, and we can show that
\nany 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<\/em> problem in NP is polynomial-time reducible to T.<\/p>\n
\nthere are a lot of different NP-complete problems that you can use as a springboard for proving that
\nyour new problem is also NP complete.<\/p>\n