Friday, 28 November 2008

The “P vs. NP” problem

One of the most contentious issues in not only computer science, but mathematics as a whole is the “P vs. NP” problem. The progress made on this problem is thus far limited to demonstrating that certain processes such as diagonalsation do not work. It is unlikely that any ``natural proof'' in the substance of Razborov & Rudich’s, ``Natural Proofs,'' (1997) will solve the issue.

The class P is defined as the class of decision problems solvable deterministically in polynomial time. The class NP is the class of decision problems solvable non-deterministically in polynomial time. This is important as polynomial differences in running time are considered small, exponential differences large. All reasonable deterministic computational models are polynomial equivalent. However, some solutions need to be determined through “brute force”.

We define this by stating that “P is the class of languages that are decidable in polynomial time on a single-tape Turing machine”. NP conversely is “the class of languages that have polynomial time verifiers”. The distinction is thus P is a class of languages for which membership may be decided quickly and NP is the class of languages which may be verified quickly.

The N v NP conjecture and the question as to whether one-way functions exist invites speculation due to the importance of the P and NP classes in a variety of fields (not least of which includes complexity studies). If it may indeed be demonstrated that P = NP is true, all complexity classes based on NP would collapse to P.

P is contained in NP by definition. The containment is believed to be proper in that there are problems where finding a short proof is super-polynomially more difficult than verifying the proof. It could be the case that P = NP is true, though the algorithms for solving NP-difficult problems in polynomial time are computationally intractable.

Most important to online commerce and the security of online systems, if P = NP is demonstrated, most of the cryptosystems currently in use would be rendered ineffective. This is directly due to the assumption that certain problems are difficult and computationally expensive to solve.

If P = NP, factoring could be done in deterministic polynomial time. This would be an advantage to many within the scientific community. The existence of an efficient factoring algorithm does not in any deterministic manner imply P = NP. Thus the factoring problem parts with NP-complete efforts.

It is known that P = NP if any one NP-complete problem is in P. Thus if there is found any P which does not equal NP, there may be no NP-complete problem in P. Some theorists hypothesize that the problem of P versus NP might be independent of the axioms of set theory and hence in principle not resolvable. So far, no single language in NP that is not in P has been proved to exist.

Cook and Levin discovered certain problems in NP where the individual complexity of the problem is related to the entire NP class. These are known as NP-Complete. If it is found that a polynomial time algorithm exists for any of the NP-Complete class, than all problems in the class NP will be solvable in polynomial time.

No comments: