39.4 P = NP

Reductions

It turns out that space-time-bounded compression reduces to 3SAT, INDSET, LONGESTPATH, and many other hard problems. (The actual proof of such reductions is incredibly complex and ommitted from this textbook).

The reason that space-time-compression can be turned into longest paths (or any other problem mentioned above) is that all these problems are part of a complexity class known as NP. A property of such problem is that any NP problem can be reduced to any NP-complete problem, including longest paths.

In subsequent section, we will briefly cover what P, NP, and complexity classes are. However, most of these topics are far beyond the scope of this textbook or course, and would be better served by taking an upper-level algorithms course.

P and NP

All yes/no problems can be divided into two main classes:

  • P: efficiently solvable problems.

  • NP: problems with solutions that are efficiently verifiable. This means that given an answer to the problem, you can efficiently check whether the answer is correct or not.

Examples of problems in P include (note that P is a subset of NP):

  • Is this array sorted?

    • This can be solved by sorting the array using any sorting algorithm, and verified by checking that adjacent elements are increasing.

  • Does this array have duplicates?

    • This can be solved with a double for-loop, and verified in a similar manner.

Examples of problems in NP include:

  • Is there a solution to this 3SAT problem?

    • Generating a solution to a 3SAT problem is difficult, but given an assignment of symbols to booleans, you can simply plug in the values and check that the equation is satisfied.

  • In graph G, does there exist a path from s to t of weight > k?

    • Genearting a solution to this (essentially longest paths) is difficult, but given a path, you can easily verify if it is a valid path from s to t and that its weight is > k.

Examples of problems not in NP include:

  • Is this the best chest move I can make next?

    • There is no efficient way to verify that a chess move is indeed optimal, unless you draw out all possibilities for all subsequent moves.

  • What is the longest path?

    • This is not a yes-no question.

NP-Completeness

An unexpected property of NP problems is that every NP problem reduces to every NP-complete problem. This reduction is also "efficient", in that the problem can be transformed (pre-processed and post-processed) in polynomial time.

This also means that solving any NP-complete problem essentially solves all problems in NP. As of today, there are tens of thousands of known NP-complete problems, but none of them have been solved yet.

P = NP?

An open question in computer science is whether P = NP; in other words, are all problems with efficiently verifiable problems (NP) also efficiently solvable (P)?

One reason to suggest that P = NP might be true is that checking an answer is always efficient. Thus, given the right pruning, could we efficiently zero in on an answer?

Last updated