home | alphabetical index | |||||

## Complexity classes P and NPComputational complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem).
In this theory, the class - Is
**P**=**NP**?
If P = NP, P would encompass the NP and NP-Complete areas.
An important role in this discussion is played by the set of NP-complete problems (or
In essence, the
A
Now suppose there is an algorithm A( -
*w*is a YES instance of the decision problem if and only if there exists*C*such that A(*w*,*C*) returns YES.
non-deterministic polynomial time and we place it in the class NP. We think of the algorithm A as a verifier of proposed certificates which runs reasonably fast. (Note that the abbreviation NP stands for "Non-deterministic Polynomial" and not for "Non-Polynomial".)
To attack the
The
Although we don't know whether
All of the above discussion has assumed that - It ignores constant factors. A problem that takes time 10
^{1000}*n*is**P**(in fact, it's linear time), but is completely intractable in practice. A problem that takes time 10^{-10000}2^{n}is not**P**(in fact, it's exponential time), but is very tractable for values of*n*up into the thousands. - It ignores the size of the exponents. A problem with time
*n*^{1000}is**P**, yet intractable. A problem with time 2^{n/1000}is not**P**, yet is tractable for*n*up into the thousands. - It only considers worst-case times. There might be a problem that arises in the real world. Most of the time, it can be solved in time
*n*, but on very rare occasions you'll see an instance of the problem that takes time 2^{n}. This problem might have an average time that is polynomial, but the worst case is exponential, so the problem wouldn't be in**P**. - It only considers deterministic solutions. There might be a problem that you can solve quickly if you accept a tiny error probability, but a guaranteed correct answer is much harder to get. The problem would not belong to
**P**even though in practice it can be solved fast. This is in fact a common approach to attack**NP**-complete problems. - New computing models such as quantum computers, which also work probabilistically, may be able to quickly solve some problems not known to be in
**P**.
P = NP.
// Algorithm that accepts the NP-complete language SUBSET-SUM. // // This is a polynomial-time algorithm if and only if P=NP. // // "Polynomial-time" means it returns "YES" in polynomial time when // the answer should be "YES", and runs forever when it's "NO". // // Input: S = a finite set of integers // Output: "YES" if any subset of S adds up to 0. // Otherwise, it runs forever with no output. // Note: "Program number P" is the program you get by // writing the integer P in binary, then // considering that string of bits to be a // program. Every possible program can be // generated this way, though most do nothing // because of syntax errors. FOR N = 1...infinity FOR P = 1...N Run program number P for N steps with input S IF the program outputs a list of distinct integers AND the integers are all in S AND the integers sum to 0If P = NP, then this is a polynomial-time algorithm accepting an NP-Complete language. "Accepting" means it gives "YES" answers in polynomial time, but
is allowed to run forever when the answer is "NO". Perhaps we want to "solve" the SUBSET-SUM problem, rather than just "accept" the SUBSET-SUM language. That means we want it to always halt and return a "YES" or "NO" answer. Does any algorithm exist that can provably do this in polynomial time? No one knows. But if such algorithms do exist, then we already know some of them! Just replace the IF statement in the above algorithm with this:
IF the program outputs a complete math proof AND each step of the proof is legal AND the conclusion is that S does (or does not) have a subset summing to 0 THEN OUTPUT "NO" (or "NO" if that was proved) and HALT ## External links and references
- The Clay Math Institute Millennium Prize Problems
- A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll.
*Automata, Languages, and Programming*, Springer LNCS 115 (1981) 278-293 and*J. Comb. Th. A*31 (1981) 199-214. - E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
- Computational Complexity of Games and Puzzles
- Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002
- The "PRIMES is in P" FAQ
| |||||

copyright © 2004 FactsAbout.com |