What this covers

Scott Aaronson discusses how computational complexity — the study of what can be solved efficiently — serves as a unifying lens across computer science, mathematics, and fundamental physics. The conversation centers on the gap between problems that are hard to solve but easy to verify (the P versus NP question), the power and limits of quantum computers, and a surprising application: how complexity arguments may resolve paradoxes in black hole physics. Aaronson explains the concrete dividing line between tractable and intractable problems, shows why quantum computers are unlikely to magically solve all hard problems, and sketches how recent work in quantum gravity has begun to speak the language of qubits and computational difficulty.

The episode ranges across several distinct territories. It covers the history of why efficiency matters more than mere computability, the universality of NP-complete problems (why thousands of practical hard problems are secretly equivalent), and why factoring stands as an exceptional case. A major thread concerns BQP — the class of problems quantum computers can solve in polynomial time — and the widespread misconception that quantum machines bypass difficulty. The conversation also turns to black holes: how the firewall paradox might dissolve if the computation needed to detect it requires exponential time longer than the black hole's lifespan, and more broadly how complexity bounds may protect effective field theory from paradox. Along the way, Aaronson addresses deeper questions about whether mathematics reflects discovery or invention, and whether Penrose's arguments about human creativity surviving against machine simulation survive scrutiny.

Sharpest takeaway

Aaronson argues that computational complexity — not mere computability — is the deep organizing principle for understanding what can be efficiently solved, and that this same notion (especially the gap between checking and finding, and quantum vs. classical resources) now illuminates fundamental physics problems like the black hole firewall paradox.

  • The crucial dividing line is polynomial vs exponential scaling, which depends on the laws of physics and is largely invariant to machine details
  • Quantum computers (BQP) and easily-checkable problems (NP) are likely incomparable, so quantum computers won't magically solve all NP-complete problems
  • Harlow-Hayden showed the firewall-detecting computation is exponentially hard, suggesting complexity bounds protect effective field theory

The argument · threads9 threads · 37 claims
0.70

Efficient computability, not whether problems are computable at all, is the fundamental question.

4 pointscentrality 5/5
  • The digital computer revolution of the 1950s and 60s revealed that the much more important question than whether something is computable at all is whether it is efficiently computable — solvable in a way that avoids brute-force checking of astronomically many possibilities — an insight Turing and von Neumann largely missed.

    “I think it was the actual digital computer revolution that made people realize that, often, the much more important question than just is something computable at all, is is it efficiently computable? Is it computable in a way that avoids a brute force checking of astronomically many possibilities?”

  • In theoretical computer science, computational complexity refers to the resources (most fundamentally time and memory/space) needed to solve a problem, and crucially what matters is how those resources scale with problem size, not absolute figures that depend on the particular machine used.

    “what people mean by complexity, let's say, by computational complexity is the resources that are needed to solve some problem, and specifically, what we care about is the scaling of the resources”

  • The practical dividing line in complexity is whether a problem is solvable by an algorithm with polynomial scaling versus requiring exponential scaling; exponential growth becomes intractable so fast that even a 1000-digit problem would take longer than the age of the universe with every atom in the observable universe working in parallel, whereas polynomial algorithms can usually be improved with effort to low powers.

    “by the time you're at problems of size 1000 or 1000-digit numbers that you'd already be talking longer than the age of the universe to solve it, even if you had every atom in the observable universe working on your problem in parallel”

  • When you cannot prove an algorithm is the best possible, you can often prove a theorem showing that improving your problem's algorithm would simultaneously improve a thousand other problems no one knows how to improve, thereby demonstrating a more fundamental difficulty rather than personal failure.

    “I can prove a theorem that says, if you could improve that to N to the 2.3 then here are a thousand other problems where you could also improve over the best that anyone knows”

0.70

NP-complete problems form a universal equivalence class where polynomial algorithm for one solves all.

4 pointscentrality 5/5
  • 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.

    “what NP-completeness means is that you show that your one specific problem has the property that if anyone could solve it in polynomial time, then P would equal NP, then you could solve every NP problem in polynomial thought”

  • Because NP-complete problems are universal, one can encode enormities into them — designing millions of boxes that fit into a car trunk if and only if there is a short proof of the Riemann hypothesis, or such that fitting them requires breaking a cryptographic code — which is why an easy intuition that real-world NP-complete instances are easy is misleading: if P equaled NP you could mine billions of dollars of Bitcoin or compress all of Wikipedia optimally, which would require deeply understanding human knowledge.

    “I could design some millions of boxes of different dimensions that would have the property that you can fit these boxes into your trunk and have it closed if and only if there is a proof of the Riemann hypothesis”

  • 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.

    “A problem is in NP if whenever the answer to it is, yes, meaning like, yes, there is a solution, then someone can show you the solution and you could check the solution using a polynomial-time algorithm”

  • 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.

    “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”

0.70

P versus NP cannot yet be proven despite sixty years of effort, though empirical evidence suggests they differ.

4 pointscentrality 5/5
  • 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.

    “polynomial time is contained in polynomial space, which is contained in exponential time. And the reason polynomial space is contained in exponential time is that, well, if I have, let's say, N bits of memory, then my computer can pass through at most 2 to the N power possible states before either it halts or else it gets into an infinite loop”

  • Although complexity theory is pure math, its practitioners reason like empirical scientists with Bayesian priors: when two complexity classes have been studied for 60 years and every theorem narrowly avoids making them equal, one rightly suspects a deep reason they are different — just as physicists treat quantum mechanics or no-superluminal-signalling as well-supported assumptions rather than proven facts.

    “even though this is pure math, the way that we approach it has some elements of empirical science also. Physicists don't prove that there's no superluminal signalling, they don't prove that quantum mechanics is correct. These are taken as very well-supported assumptions”

  • 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.

    “if you could prove that P were equal to NP and, furthermore, your algorithm was actually efficient in practice... well, then, yeah, you could not only collect a million dollars for solving that problem but you could also solve the other six problems”

  • Complexity classes can be anthropomorphized as having distinct personalities like comic book superheroes, each with a different set of powers; some are clearly more powerful than others, while others have bizarrely incomparable powers that make comparing them like asking who would win between Godzilla and Batman.

    “Each one has a personality. They're like comic book superheroes. Each one has a different set of powers... you get two classes with just bizarrely incomparable powers”

0.68

Quantum computers exploit interference patterns to achieve polynomial speedups in special cases like factoring.

7 pointscentrality 4/5
  • While Turing's notion of computability is invariant to the details of physics — classical or quantum, any number of spatial dimensions — the notion of efficient (polynomial-time) computability is more physics-dependent, and changing the laws from classical to quantum appears to enlarge what is computable in polynomial time, which is what led David Deutsch to invent quantum computing.

    “Turing's definition of computability in the 1930s had this amazing invariance to the details of physics... But once we ask about efficient computability, polynomial-time computability... changing the laws of physics from classical to quantum, that does seem to be enough to enlarge what is computable in polynomial time”

  • In the black-box (query complexity) model, quantum computers have provable advantages over classical ones, including exponential and super-exponential separations; Aaronson and Ambainis proved a problem solvable with a single quantum query that requires about square-root-of-N classical queries, and showed this is the largest possible gap, though query complexity is a 'perturbation-theory' playground rather than a real-world proof.

    “In this model of query complexity, here, we really do have proven advantages of quantum computers over classical ones... There are problems involving end bits of input where it takes square root of... About square root of N queries to solve them classically, and they can be solved with only one query with a quantum computer”

  • Peter Shor's 1994 algorithm showed that factoring an n-digit number, the basis of most modern encryption, lies in BQP — solvable on a quantum computer in roughly N-squared operations — versus the best known classical algorithm (the number field sieve) which takes time growing exponentially in roughly the cube root of N; this exploits special structure from group theory, number theory and the Fourier transform, not mere parallel-universe trial of every divisor.

    “Shor showed that the factoring problem is in BQP... if you could build a quantum computer then you could factor an n-digit number using a number of elementary operations that only scales like N squared, roughly”

  • A quantum computer's power comes from the fact that to describe the state of just 1000 qubits requires a list of 2-to-the-1000 complex amplitudes — one for every possible configuration — making the underlying objects enormously larger than classical bit-strings and opening the potential to compute more in polynomial time, captured by the class BQP (bounded-error quantum polynomial time).

    “if I have, let's say, 1000 qubits, 1000 quantum bits, then just to describe their state, I need a list of 2 to the 1000 complex numbers. I need a quantum mechanical amplitude for every possible configuration”

  • Grover's algorithm can search an unstructured list of N possibilities in about the square root of N steps (versus N/2 classically), so layering it on a classical NP-complete search can reduce a 2-to-the-100 step problem to roughly 2-to-the-50 steps — a real and useful but merely quadratic, not exponential, speedup.

    “there is a quantum algorithm that can search a list of N possibilities in only about the square root of N steps”

  • The central trick behind every quantum algorithm is choreographing an interference pattern of amplitudes — which unlike probabilities can be negative or complex — so that contributions to wrong answers cancel out while contributions to the right answer add constructively, all without knowing in advance which answer is correct and fast enough to beat classical brute force; merely creating a superposition over all answers and measuring just yields a random answer.

    “the central trick in quantum computing, the trick behind every single quantum algorithm is this, that you are trying to choreograph a pattern of interference of these amplitudes, where for each wrong answer... some of those contributions should have positive amplitude, and some should have negative amplitude... And so they mostly just cancel each other out. Whereas for the right answer... you would like all of the contributions to its amplitude to be pointing the same way”

  • 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.

    “BQP contains classical P, or in other words, a quantum computer can always efficiently simulate a classical computer... you could use a space shuttle to taxi around the parking lot”

0.56

The uncomputability of the halting problem does not prohibit machines from matching or exceeding human mathematical ability.

4 pointscentrality 4/5
  • Penrose's argument (updating Lucas) that human creativity can never be simulated by a machine fails because it requires the further unjustified step that humans are 'perfect mathematicians' who can infallibly see the consistency of formal systems; once you grant a machine the same liberties humans have — to learn from experience, make mistakes, and say 'I don't know' — there is nothing math or logic can say against a machine doing as well as or better than a human.

    “as soon as you grant a machine the same liberty that it can try to learn from experience, it can make mistakes sometimes, it can sometimes just give up and say, "I don't know," then there is no longer anything that math or logic can say against the machine doing just as well as a human does, or better than a human does”

  • One of Turing's great discoveries, alongside the Turing machine, was that not everything is computable: there are well-defined problems for which no algorithm can solve them in any amount of time, the most famous being the halting problem of deciding whether an arbitrary program ever stops.

    “One of Turing's great discoveries along with the invention of the Turing machine was the discovery that not everything is computable. There are problems where you can just prove that there is no algorithm to solve them in any amount of time.”

  • The halting problem encodes a large fraction of mathematics because one can write a program that enumerates the zeros of the Riemann zeta function and halts only if one is found off the critical line, so determining whether that program halts is equivalent to solving the Riemann hypothesis — and the same construction applies to many great unsolved problems.

    “we could write a program that just will enumerate over all the zeros of the Riemann zeta function and will halt only if there is one that is not on the critical line. Now that is a program where to determine whether that program halts or runs forever is equivalent to solving the Riemann hypothesis”

  • The uncomputability of the halting problem does not imply human mathematicians can never be beaten by machines; it only means that if machines do beat them, the machines won't be perfect either, since math depends on creativity that no infallible algorithm possesses.

    “Which doesn't mean, by the way, that human mathematicians could never be beaten by machines. It just means that if they are, then the machines won't be perfect either.”

0.44

Quantum gravity physics is increasingly framed using quantum information language like qubits and complexity.

8 pointscentrality 2/5
  • Harlow and Hayden gave evidence that the quantum computation required to detect the relevant correlations in Hawking radiation — needed to provoke the firewall — would take a number of steps exponential in the number of qubits of the black hole, meaning roughly 2-to-the-(10-to-the-67) years, so you could not make a dent in the computation before the black hole itself evaporated, plausibly dissolving the paradox.

    “they gave evidence that to actually do the quantum computation on the Hawking radiation that would detect those correlations... would require a quantum computation that would use a number of steps that is exponential in the size of the black hole”

  • Harlow and Hayden's subtle point is not that contradictions are acceptable if hard to discover, but that the contradictions in effective field theories (which must ultimately be superseded by quantum gravity) may surface not at extreme energies or tiny distances but in regimes of extreme computational complexity; if exposing such a breakdown requires an exponential computation, then we have a principled reason to trust effective field theory in normal situations.

    “it might be that some of these problems with effective field theories, you would find them not by going to an enormously high energy or to an enormously tiny distance, but by going to a regime of extreme computational complexity. But if it would take an exponential computation to uncover the breakdown of effective field theory, then we do have a reason for trusting our effective field theory in "normal situations."”

  • High-energy physics, despite its 20th-century triumphs, is a 'very tall and narrow tower of knowledge' where immense brainpower is expended on a narrow set of questions; with the LHC having found only the Higgs and nothing else, a young scientist without their heart set on it might do better exploring newer fields like quantum information that are full of low-hanging fruit.

    “there is an immense amount of brain power that is being expended on not a huge set of questions on a very narrow... Let's say a very tall and narrow tower of knowledge”

  • A black hole has the largest entropy of any object of its size — it is the highest-density hard disk allowed by the laws of physics, storing about 10-to-the-69 qubits per square meter of event-horizon surface area — though it is useless for retrieval since bits emerge only as scrambled Hawking radiation over perhaps 10-to-the-70 years.

    “a black hole has an entropy. Not only does it have an entropy, but it has the largest entropy of any object in the universe of a similar size. You could say a black hole is the highest density hard disk that is allowed by the laws of physics. Specifically, it stores about 10 to the 69 bits or rather 10 to the 69 qubits per square meter of surface area of its event horizon.”

  • The 2012 AMPS firewall paradox showed that a small set of seemingly-true postulates — including that an infalling observer notices nothing special crossing the event horizon and that black holes rapidly scramble information — implies a contradiction: an observer who measures subtle correlations in Hawking radiation after a black hole is more than 50% evaporated and then jumps in would either see quantum mechanics break down or hit a wall of ultra-high-energy photons (a firewall) at the horizon.

    “in 2012, this AMPS paper came along and it broke everything again... It said that if you write down certain postulates that seem like they should be clearly true... then you could write down an experiment that, in principle, some observer who was outside of a black hole could do”

  • In the AdS/CFT correspondence, circuit complexity is used as the quantity holographically dual to a geometric quantity like the volume of a wormhole; while Susskind believes complexity has fundamental physical importance like entropy or energy, Aaronson is unwilling to go that far but accepts it as the best available placeholder for whatever quantity is truly dual to these wormhole volumes.

    “in this AdS/CFT correspondence, where you literally use circuit complexity as the thing that is holographically dual to some geometric quantity, like the volume of a wormhole”

  • Whether a scalable quantum computer can be built is not merely an engineering problem but a fundamental question of whether nature will allow an exponential computational speedup at all, or whether there is something not yet understood about quantum mechanics that would prohibit it — which is part of why high-energy physicists like Preskill found the field compelling.

    “This is a fundamental question of, does... Is nature going to allow this at all? Can a scalable quantum computer be built? Or is this so ridiculous that we should just suppose that there is something about quantum mechanics that we have not yet understood that is going to prohibit getting an exponential computational speed-up in this way?”

  • Within the last eight or nine years something remarkable happened: researchers studying quantum gravity, the black hole information problem, AdS/CFT, and holographic spacetime now discuss them largely in the language of qubits, quantum gates and circuits, entanglement structure, and complexity — so much so that much of recent Strings Conference content is effectively quantum information rather than strings.

    “within the last eight or nine years, something really amazing has happened, which is that the things really have circled back and the people who talk about quantum gravity these days... they are talking about it largely in a language of qubits and qugates, quantum circuits acting on those qubits, and entanglement... and even complexity”

0.35

Containment relationships between complexity classes hold, though strict containment of P in PSPACE remains unproven.

2 pointscentrality 3/5
  • 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.

    “if P were equal to PSPACE, that would mean that perfectly playing all these games would also be a problem that you could solve in a small amount of time”

  • 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.

    “P is contained in BQP... We also know that BQP is contained in PSPACE... that means that in terms of running time in the real world, quantum computers could, at most, give you an exponential advantage over classical ones. So they're not going to solve the halting problem.”

0.35

Mathematics is constrained by objective truth rather than cultural convention, revealed through logical resistance.

2 pointscentrality 3/5
  • Doing mathematics is a push-back against something external that can tell you that you were wrong — it has constraints not of your own making — which makes it like empirical science and is why most mathematicians are in practice Platonists while working, even if they deny it later.

    “to do math is a push back against something that can tell you that you were wrong. It's not just a thing that you were making up. It is a thing that has constraints that are external to you. And in that way, it is like empirical science.”

  • Mathematics is not merely an arbitrary cultural creation but is constrained by logic and truth, so an extraterrestrial civilization would agree with us about the Pythagorean theorem and would independently discover the same fundamental objects — integers, Euclidean space, complex numbers, symmetry groups — because these concepts are so ubiquitous that any sufficiently deep inquiry must reinvent them, even if human-specific inventions like chess or AES encryption would not be shared.

    “if we ever encounter an extraterrestrial civilization and we are able to communicate with them, I think that they will agree with us about the Pythagorean theorem. I think that they will have discovered much of the same math as we have discovered.”

0.21

Popular discourse conflates NP with BQP, falsely suggesting quantum computers solve all hard problems easily.

2 pointscentrality 2/5
  • Quantum computing, especially in the 1990s, was a field full of low-hanging fruit and fundamental questions, making it attractive for young researchers to make a mark.

    “Quantum computing, especially in the '90s, was a field that was just full of low-hanging fruit and I think really fundamental questions”

  • 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.

    “the biggest mistake that popular writers make when they write about quantum computers, and this has been true for 25 years by now... is that they conflate NP with BQP”