P vs. NP
our different classes A and B, class A actually represents P which stands for polynomial time and B for NP which stands for non-deterministic polynomial time. This is what P vs. NP is. The problem is whether easily verifying a solution, and easily producing a solution, describe the same problems. 2 On the surface, it appears as if problems in NP are harder than problems in P. If a problem is in P, it must also be in NP. The question is, is the reverse also true? Namely, if a problem is in P is it also in NP? Or equivalently do both sets describe the same problems? Does P = NP? In 2000 the Clay Institute offered $1,000,000, to anyone who could answer any of seven problems. Of the so named ‘ Millennium Problems ’ , one has been solved, the Poincare conjecture, by Grigori Perelman in 2006. P Vs. NP is the most recent of these problems conjectured in 1971 and is still to be solved. In the 1970s computer scientists were figuring out how to program their chunky computers to solve all the world’s problems. Usually, the first solution thought for a problem would be unworkably slow, but then over time people would come up with more intuitive, faster, and more efficient solutions, Mostly. For some problems, there was a concrete wall. Nobody was coming up with faster programs. For programs like multiplication, they already had fast and effective programs. But for harder problems like Chess (which is now considered in a supergroup called exptime), they had no solutions, at least no fast ones. For a bunch of problems in between, they weren’t sure. Problems like finding primes or the travelling salesman problem. This is where the sets P and NP originate. Let’s go back to the meaning of P and NP. What does non -deterministic mean? Simply put, and this is very simply put, if in our jigsaw puzzle example you had a computer that could simulate all possible chains of events at once, then you could find a solution in polynomial time. Problems in NP can only be checked in polynomial time, and problems in P can be solved in polynomial time. With this we can define with rigour which problems are in P. We can say that a decision problem is in P if and only if there is a polynomial-type algorithm that returns 1 for all inputs that have a ‘ yes ’ answer to the decision problem and returns 0 for all inputs that have a ‘ no ’ answer. More formally:
L ∈ P iff ∃ M s.t. M ∈ O(n k ) for some k
∀ x ∈ L, M(x) = 1 ∀ x ∉ L, M(x) = 0
In all, P represents the class of problems that can be decided in polynomial time. In P, if a problem is easy to check the solution to, is it also easy to find the solution? NP represents the class of problems that can be decided in polynomial time by a non-deterministic Turing machine. Verifying solutions is possible in polynomial time but deciding a solution is non-deterministic when polynomial in NP. Recall how problems in P were considered ‘ easy ’ , and problems in NP were considered ‘ hard ’ . We have to make this statement slightly more rigorous. To do this we consider all problems in P as those which have a solution that runs in polynomial time, or in O(n k ). Those in NP have running time Ω(n k ). Ω(n) expresses the lower bound of an algorithm ’ s running time, so as to say, all problems in NP run more slowly than or equal to O(n k ). The jigsaw puzzle, for example, is a problem in NP since only checking the
2 Algorithms - What exactly is polynomial time? [online] Available at: https://cs.stackexchange.com/questions/13625/what-exactly-is-polynomial-time.
158
Made with FlippingBook interactive PDF creator