P
The complexity class of problems solvable in polynomial time; informally, the 'efficiently solvable' problems.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 1
Most important claims · 7 of 7Search all claims for “P” →
- P versus NP is the most important of the seven million-dollar Clay problems because if P equaled NP with an efficient algorithm (like N-squared), you could program a computer to find short formal proofs and thereby solve the other six Clay problems, steal 200 billion dollars of Bitcoin, and proceed toward world domination.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- The big surprise of the early 1970s was NP-completeness: most hard problems in NP have a universality property whereby a polynomial-time algorithm for any one of them would solve every NP problem in polynomial time, so the thousands of practical hard problems (airline scheduling, traveling salesperson, combinatorial optimization, even Super Mario levels) are all equivalent, while factoring is a rare outlier living in a no-man's land between P and NP-complete.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- If polynomial time equaled polynomial space, then perfectly playing two-player games of perfect information like chess or Go — which can be solved with small memory by traversing the exponentially large game tree — would also become solvable in a small amount of time, yielding a super-efficient algorithm to play any such game perfectly, which is why we doubt P equals PSPACE.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Because P is contained in BQP which is contained in PSPACE, quantum computers can give at most an exponential running-time advantage over classical ones and cannot solve anything uncomputable like the halting problem; moreover, proving P is not equal to BQP would require proving P is not equal to PSPACE, explaining why a real-world quantum advantage cannot yet be proven.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Polynomial time (P) is contained in polynomial space (PSPACE), which is contained in exponential time, because a serial computer using N bits of memory can pass through at most 2-to-the-N states before halting or looping; we believe each containment is strict but have only proven that exponential time is strictly larger than polynomial time.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- A quantum computer can always efficiently simulate a classical computer, so P is contained in BQP — like using a space shuttle to taxi around a parking lot, possible but not the point.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- For the last half century no one has been able to prove that any NP problem is actually hard — that is, we cannot prove P is not equal to NP — and we don't even know that factoring is hard, only that we believe it is.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity