NP-hard
A class of problems (like the traveling salesman problem) for which a proposed solution can be verified efficiently but finding one appears intractable; solving one efficiently would solve many optimization problems efficiently.
As defined in 153 | John Preskill on Quantum Computers and What They're Good For
Where it comes up · 3
- 153 | John Preskill on Quantum Computers and What They're Good For2 claims
- The coming AI revolution and the question no one can ignore | Max Tegmark | Strange Loop1 claim
- Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch1 claim
Most important claims · 4 of 4Search all claims for “NP-hard” →
- 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
- 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
- The profound accomplishment of AlphaGo is that roughly ten sequential layers of neural-network computation can amortize and approximate to high fidelity a nearly intractable, NP-class search problem—suggesting our worst-case-complexity framing of hard problems may be incomplete, since hard problems often have exploitable structure.Dwarkesh Patel Podcast - Eric Jang – Building AlphaGo from scratch
- The task of automatically figuring out what formula a neural network has learned is called symbolic regression, and while it's generally believed to be NP-hard (could take longer than the age of the universe), Tegmark's group managed to get state-of-the-art performance by using ideas from physics to discover whether neural networks are modular and can be decomposed into smaller pieces.The coming AI revolution and the question no one can ignore | Max Tegmark | Strange Loop