factual

We Cannot Prove Any NP Problem Is Hard

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.

factualpending

Speaker

Scott Aaronson

Evidence Quote

“we don't know that any NP problem is hard. This has been the situation for the last half century that we, famously, we cannot prove that P is not equal to NP”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...