P versus NP
A foundational question in computer science about whether problems whose solutions can be quickly verified can also be quickly solved; many logistics optimizations fall into the hard (NP) category.
As defined in 171 | Christopher Mims on Our Interconnected Industrial Ecology
Where it comes up · 6
- Lex Fridman Podcast #503 - AI Crisis in Math2 claims
- 153 | John Preskill on Quantum Computers and What They're Good For2 claims
- Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study2 claims
- 171 | Christopher Mims on Our Interconnected Industrial Ecology1 claim
- AMA | April 20251 claim
- AMA | September 20221 claim
Most important claims · 9 of 9Search all claims for “P versus NP” →
- Logistics is saturated with high-stakes mathematics because a fraction-of-a-percent efficiency gain saves tens of millions of dollars; firms invest enormously (UPS spent $300 million ~20 years ago on its Orion routing software) to approximate solutions to intractable, NP-hard problems like the traveling salesman that could never be solved exactly before the heat death of the universe, with predictive analytics being one of the best mundane applications of machine learning.171 | Christopher Mims on Our Interconnected Industrial Ecology
- We cannot prove from first principles that factoring or quantum simulation problems are classically hard—factoring is not even known to be NP-hard; our confidence rests on the empirical fact that very smart people have tried for decades to find better classical algorithms and failed, which means a brilliant student could in principle discover an efficient classical algorithm tomorrow.153 | John Preskill on Quantum Computers and What They're Good For
- Moitra states that although SAT is believed to require exponential time, researchers know no lower bound on satisfiability that is asymptotically more than the time needed to read the input, which he calls a striking gap in understanding.Lex Fridman Podcast #503 - AI Crisis in Math
- There are fairly convincing arguments that quantum computers will not be able to efficiently find exact solutions to NP-hard problems like the traveling salesman problem; they can speed up exhaustive search only quadratically (square-root of the classical time), which is far less spectacular than the super-polynomial, nearly exponential speed-up they provide for factoring.153 | John Preskill on Quantum Computers and What They're Good For
- Computer-science 'complexity theory'—which classifies problems by how time and memory resources scale with input size (e.g. P vs NP)—is a distinct, tightly-defined field that merely shares a name with Santa Fe Institute-style 'complexity theory'; the latter, studying complex adaptive systems, lacks a similarly crisp characterization of which problems fall inside it, making it more of a loose interdisciplinary cluster than a precisely bounded area.AMA | April 2025
- Good early wrote to Feynman in 1956 (when Feynman was dying) proposing the first formulation of the P versus NP problem, which remained unanswered and became a Millennium Prize Problem, highlighting a 70-year continuity of interest in the computational limits of classical machines.Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study
- The P versus NP problem is one of the Millennium Prize problems and the most fascinating problem in computer science and applied mathematics because it gets to the heart of what is fundamentally possible to compute on classical machines.Sir Demis Hassabis on The Future of Knowledge | Institute for Advanced Study
- P versus NP asks whether problems whose solutions can be checked quickly (NP) are the same class as problems that can be solved quickly (P); to say P does not equal NP is to say some problems are hard to solve but easy to check, which all sensible people believe, because a world where P equals NP would make implausible things like axiomatizing creativity easy, so Carroll sees lots of reasons to think P is not equal to NP and none to think otherwise, though no proof yet exists and there is no deadline.AMA | September 2022
- Moitra explains P versus NP: problems whose solutions can be verified in polynomial time are NP, and the question is whether they can always be solved in polynomial time; the presumption is no, and most of modern cryptography relies on that presumption.Lex Fridman Podcast #503 - AI Crisis in Math