Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

7.2 P versus NP > 7.2 P versus NP - Pg. 147

Polynomial-Time Computability 147 Example: The set of three-colorable graphs (as a set of binary strings) is in NP. A graph w is three-colorable iff there exists some three-coloring y, such that w is properly colored by y (that is, adjacent vertices are always different colors). Similarly, the set of Hamiltonian graphs is in NP. Here, the evidence y is a Hamil- tonian cycle in the graph w. Another example of a language in NP is SAT, the set of satisfiable formulas of sen- tential logic. The truth-table method taught in logic courses for determining whether a formula with n sentence symbols is satisfiable involves forming all 2 n lines of the formula's truth table, and looking to see if there is a line making the formula true. But this is not a feasible algorithm because 2 80 microseconds greatly exceeds the age of the universe. But if we (nondeterministically) guess the correct line of the table, then we can quickly verify that the formula is true under that line. There is a clear analogy between computable and recursively enumerable (r.e.) sets on the one hand, and P and NP on the other hand. The computable sets are decidable; the sets in P are decidable by fast algorithms. And r.e. sets are one existential quantifier away from being computable; sets in NP are one existential quantifier away from being in P. Moreover, there are r.e. sets that are complete with respect to m ; there are NP sets with a similar property. Say that L 1 is P-time reducible to L 2 (written L 1 P L 2 ) if there is a P-time computable (total) function f that many-one reduces L 1 to L 2 . The following result was proved independently by Cook (1971) and Leonid Levin (1973):