NP
The complexity class of problems whose 'yes' answers can be verified in polynomial time given a proposed solution; stands for non-deterministic polynomial.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 1
Most important claims · 5 of 5Search all claims for “NP” →
- The biggest mistake popular writers have made about quantum computers for 25 years is conflating NP with BQP — writing as if a quantum computer is a magical machine for solving all NP problems by trying each answer in a parallel universe — when in fact NP and BQP are believed to be incomparable, factoring was a lucky special case, and typical exponentially hard problems remain exponentially hard on a quantum computer.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- 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
- A problem is in NP if, whenever its answer is yes, a solution can be exhibited and verified in polynomial time — like a completed jigsaw puzzle, prime factors that can be checked by multiplying, a solved Sudoku, or an optimization solution shown to a client — capturing the asymmetry between hard-to-solve but easy-to-check problems.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