The P-NP Problem

This is an introduction to one of the greatest unsolved problems in theoretical computer science. If you have studied computer science at university, you will have probably already heard about it. For others, this article might help broaden their intellectual horizon.

Written by Claus Volko
Vienna, Austria, Europe

Contact: cdvolko (at) gmail (dot) com
Homepage: www.cdvolko.net

The P-NP-problem is one of the most difficult unsolved problems in computer science. It is one of the Millennium Prize problems, and the first person to solve it will receive $1 million dollars from the Clay Mathematics Institute.

P and NP are sets of decision problems that have a certain complexity. Therefore P and NP are also colloquially known as complexity classes, although this term is not quite correct.

A problem belonging to one of these set means that there is an algorithm which solves the respective decision problem and its duration will not exceed a given limit even in the worst case.

If the decision problem corresponding to an algorithm belongs to class P, the algorithm needs only a polynomial number of steps with regard to the size of the input data, no matter which input data you use (that is, a constant multiplied by the size of the input data to the power of another constant). By contrast, NP means that it is possible to check for correctness of a solution in polynomial time relative to the size of the solution.

Any algorithm that is in P is also in NP. If you have the solution for a given problem in P, it is also possible to verify this solution in a polynomial number. of steps. The question is whether it is also possible the other way round. Most computer scientists think no. But should it turn out that each problem in NP is also in P, that would be a true revolution, because then the computation of many problems would accelerate significantly.

To prove that P and NP are equal, it would be enough to prove for a single NP-complete problem that it is also in P. NP-complete problems make up a subset of NP, with the property that they are at least as difficult as any are another problem in NP. A problem for which this property has been proven, is the satisfiability theorem of propositional logic (SAT, theorem of Cook and Levin).

To show that another problem is NP-complete as well, it's enough to prove that it's in NP, and that it's at least as difficult as SAT. The latter can be achieved by finding a way to reduce SAT to this problem, i. e. by finding a way of how an algorithm for this problem could be used to solve SAT.

So far, not a single polynomial algorithm has been found for an NP-complete problem. It seems more realistic to find evidence that P is not equal to NP but this search is also very difficult. A possibility would be to show that there is no algorithm at all for a certain NP-complete problem. with polynomial runtime, but how should this be done?

Proving that something is not feasible seems to be much more difficult than that to prove the opposite, and for this reason the P-NP problem is still considered unsolved.

The original German language version of this article was first published in MATHEMATIQ 3, from 2013.

Claus Volko