Scott Aaronson on Computational Complexity, Consciousness, and P vs NP

High-Level Overview

In his second appearance on the Lex Fridman Podcast, quantum computer scientist Scott Aaronson (professor at UT Austin, director of its Quantum Information Center, and formerly at MIT) sits down with Lex on a rain-soaked covered patio in Austin for a wide-ranging conversation about computation, consciousness, and the state of the world. They move from whether we live in a simulation, to theories of everything, to Scott's well-known takedown of integrated information theory, to Roger Penrose's quantum-gravity account of the mind, the Turing test, GPT-3, the beauty of universality, the "zoo" of complexity classes, P versus NP, and finally the pandemic, the 2020 election, cancel culture, and love.

The tone is playful and curious but rigorous. Scott is quick to deflate grand claims (his own included), explains deep ideas with everyday analogies, and is candid about what nobody knows. Lex brings a romantic, intuition-driven view of intelligence and consciousness, which gives Scott plenty to push against. The conversation swings from philosophy of mind to crisp theoretical computer science, then closes on personal and political reflection.

The Discussion Explores:

• Whether the simulation question means anything, and the sharper question of whether the universe is computable (the Church-Turing thesis)
• What a "theory of everything" really promises, and why "everything" is ambiguous
• The "pretty hard problem" of consciousness and Scott's critique of Giulio Tononi's integrated information theory (IIT)
• Roger Penrose's chain of speculations linking quantum gravity, objective collapse, and Gödel's incompleteness theorem to the mind
• The Turing test, the Eugene Goostman episode, ELIZA, and why GPT-3 is a genuine leap
• Universality as the most beautiful idea in computer science
• The Complexity Zoo: P, NP, PSPACE, BQP, SZK, and why Scott bets P is not equal to NP
• The pandemic as a failure of institutions, fears about the election, and the fight over cancel culture and open discourse

Deep Dive into Main Ideas

Simulation, Computability, and Hacking the Universe

Lex opens with the simulation hypothesis, and Scott answers with a question: what difference does it make? A perfect simulation is by definition indistinguishable from the real thing, so there would be no direct evidence of the larger universe it runs in. If the simulation were imperfect and could be hacked, he says, that would be hard to tell apart from what people would ordinarily call a world with miracles.

The better-defined question, Scott argues, is whether the world is computable: whether any physical system could be simulated to any desired precision by a Turing machine. So far the indications are strong that our world satisfies the Church-Turing thesis, or at least nobody has found why it wouldn't. Lex asks whether an AI might someday "look outside" its computer to understand its creator. Scott notes that real computers leak all the time; one memory allocation error in a C program lets code escape its sandbox, which is how most hacks work. He shares Peter Shor's joke that perhaps general relativity and quantum mechanics haven't been unified because that part of the universe was simply left unspecified, and a black-hole experiment might trigger an overflow error. Scott's Occam's-razor guess, though, is that a universe that has held up for about 14 billion years will keep holding up.

What a "Theory of Everything" Means

On Eric Weinstein and Stephen Wolfram, Scott says neither has a theory of everything; they have ideas they hope could someday lead to one. Pursuing a fundamental theory of all physical interactions is, he says, the entire program of fundamental physics, and it motivates his friends in quantum gravity and string theory. He points to Ed Witten and Lenny Susskind as mainstream figures who openly seek a unified description of nature.

Where people react badly, Scott says, is when someone suggests they cracked the problem after thinking about it for five minutes. Lex adds that even a unified physics would leave most of what humans care about, psychology included, unexplained. Scott agrees the word "everything" is ambiguous and invites debates about reductionism versus emergence; physicists who avoid the phrase may just be trying to short-circuit that debate.

The Pretty Hard Problem and the Case Against IIT

Scott distinguishes the famous hard problem (why anything feels like anything at all) from what he calls the pretty hard problem: giving a principled account of which physical systems are conscious and how much. Is a fetus conscious, and in which trimester? A dog? A frog? Such an account would be needed to decide when to regard AIs as conscious. Giulio Tononi's integrated information theory is noteworthy as a direct attempt to answer this. It defines a quantity, phi, based on how a system's components are connected. In all its variations it involves what computer scientists call graph expansion: a system scores high if it cannot be split into two weakly connected halves.

Scott has two objections. The minor one is that there is nothing even resembling a derivation of phi; postulates are stated, some verbal discussion follows, and then phi appears. The core one is that it is easy to build a system with an enormous phi, larger than a brain's, that just implements an error-correcting code, such as a huge regular grid of XOR gates, doing nothing we would associate with intelligence or consciousness. Tononi's response, Scott says, was to accept that such a system is conscious, even more conscious than a person. Scott calls it "the most audacious bullet biting I've ever seen in my career." His reply: a new theory of temperature should first confirm that boiling water is hotter than ice before we trust its surprising predictions about the sun. If a theory says a grid so uniform it might as well be a blank wall is more conscious than a person, he asks what is left for it to get right. A definition, he argues, is only good if it matches what we meant before we had it.

Is Consciousness Computation? Prediction, Free Will, and Copies

Asked whether consciousness is computable, Scott calls these the "vertiginous" questions. He feels he is conscious in a way not reducible to computation, but asks why anyone should believe him. The trouble with theories of consciousness is not just lack of progress; it's hard to say what would even count as progress, since any mechanism can be met with the objection that it doesn't explain what breathes fire into it.

Lex proposes that emulating consciousness is as good as consciousness, perhaps whenever there is a black box that looks like magic to human inspectors. Scott points out this would make consciousness relative to the observer, which he rejects: if consciousness means anything, it is experienced by the conscious entity itself. He poses the hard case of a cosmological-sized lookup table that caches every possible conversation and passes the Turing test. He then describes his essay The Ghost in the Quantum Turing Machine, written about seven years earlier, which asks whether brains might be unpredictable even in principle because chaos amplifies quantum uncertainty, for example in whether sodium ion channels open or close. If someone could reliably predict everything he would do and seal it in an envelope, he says, it might not destroy his sense of being conscious, but it would destroy his sense of free will. Whether that's physically possible depends on how deep a copy must go: a clean digital abstraction layer might allow scanning each neuron, but at the molecular level you run into the unclonability of quantum states. And if someone made a copy no one else could tell apart from you, why should anyone believe you when you insist it isn't you?

Penrose's Tower of Speculations

Scott read Penrose's books as a teenager and later discussed these ideas with him at a conference in Minnesota. He admires the audacity, but stresses that Penrose is not merely saying quantum mechanics matters to the mind. A quantum computer can still be simulated by an ordinary computer, just with exponentially more time. Penrose wants the brain to exploit unknown laws of quantum gravity that are uncomputable, even beyond an oracle for the halting problem.

Scott lays out the stacked assumptions. Quantum gravity would have to be uncomputable, which most researchers doubt given what AdS/CFT suggests. Those effects would have to matter in a brain operating at ordinary temperatures with ordinary chemistry, rather than only at black-hole singularities or the Big Bang; Sean Carroll has argued quantum field theory screens them off. Quantum mechanics would need an objective collapse mechanism (GRW is one such proposal, and Dirk Bouwmeester has worked on experiments), which alone would be the biggest development in physics in a century. Consciousness would then need to steer the direction of the collapse. Finally, the whole thing rests on an argument from Gödel's incompleteness theorem that humans can somehow "see" a formal system's consistency. Scott, like most computer scientists and mathematicians who have looked at it, doesn't find it sound: an AI could keep adding new axioms, and Gödel only says it has no guarantee of being right. Turing made the reply 70 years ago: we don't have that guarantee either.

The Turing Test, ELIZA, and GPT-3

Scott recalls being asked by journalists about Eugene Goostman, a chatbot posing as a 13-year-old boy and hailed as the first to pass the Turing test. Instead of legalistic readings of Turing's percentages, he just tried it with common-sense questions like whether Mount Everest is bigger than a shoebox, and it only parried. Eugene, he concluded, was not a significant advance over ELIZA, the 1960s therapist bot that mostly reflected users' words back and fooled many people with a few hundred lines of Lisp.

GPT-3 is a different story. Scott says it does not pass the Turing test, but is a major advance over anything seen before. It writes passable poems in a given poet's style and student essays he thinks would earn at least a B-minus. He quotes Scott Alexander's description that OpenAI "ground up the entire internet into a slurry." It is a deep net trained to predict the next word, not to decide what ought to be true. Lex pushes back that cognition itself might be that simple, and Scott agrees this is the deep philosophical question GPT-3 raises. Because GPT-3 was basically GPT-2 scaled up and noticeably better, nobody knows where the ceiling is; he guesses there must be diminishing returns but wishes he had more to base that on. Its failures are ironic: balancing parentheses, basic arithmetic, and spatial word problems. He suspects the brain couples predictive processing with other mechanisms, like visual and exact logical reasoning, that it can call as subroutines.

Universality: The Most Beautiful Idea

Asked for the most beautiful idea in computer science, Scott picks universality. As an adolescent learning Apple BASIC and GW-BASIC, he assumed that writing his dream Nintendo-style video games would require ever more powerful languages. Instead a few simple operations suffice: AND, OR, and NOT, or even just NAND, can express any Boolean function. Any language can express any other by writing an interpreter or compiler for it. Turing showed in the 1930s that a stripped-down machine that reads, writes, moves left or right, and changes state can simulate all others, and that a single universal machine can run any program placed on its tape.

Scott calls it an enormous flattening of the universe; Gödel apparently had the same infinite-hierarchy conjecture until he read Turing's paper. But it is also empowering: once you know the rules, you have the same weapons as the world's greatest programmer, and what remains is how you wield them, along with questions of resources such as time and memory.

The Complexity Zoo and P Versus NP

Complexity theory studies the inherent resources needed to solve problems. Adding numbers takes linear time; schoolbook multiplication is quadratic, though near-linear methods now exist. Factoring seems to need something close to exhaustive search; the best known algorithms are exponential in roughly the cube root of the number's size, and most internet encryption rests on the belief, not a theorem, that factoring is hard. Scott suggests 1,000-bit keys are probably breakable by intelligence agencies with a few hundred million dollars of computing, while 2,000-bit keys would be beyond them.

In 2002 he created the Complexity Zoo, which now catalogs about 500 classes, which he likens to the chemical elements of theoretical computer science. P is the problems solvable in polynomial time; NP (non-deterministic polynomial, not "not polynomial") is those whose solutions can be checked quickly. PSPACE (polynomial memory) includes deciding who wins generalized chess or Go; #P counts solutions; EXP is proven to be larger than P; BPP allows randomness; and BQP is what quantum computers can do efficiently. Using Feynman's sum-over-paths picture, Scott explains why BQP sits inside PSPACE: you can add up the amplitudes leading to one outcome while reusing the same memory for each term. His personal favorite is BQP/qpoly, quantum computing with "advice" states he helped define around 2003, which is also his Gmail address. But he argues statistical zero knowledge (SZK) is more fundamental than most realize, illustrated by a wizard who proves two graphs are not isomorphic by correctly identifying a randomly permuted graph 100 times in a row, revealing nothing about why.

On P versus NP, his bet is simple: "P is not equal to NP." He'd give P equals NP two or three percent odds, reasoning about how often he'd be right across 50 such mysteries. If P did equal NP with a practical algorithm, you could break most encryption and cryptocurrencies, find optimal neural networks, and search for short machine-checkable proofs, which is why "if you had this fast algorithm, then you could solve all seven of them" of the Clay millennium problems. He also describes Leonid Levin's dovetailing trick, which shows such an algorithm would, in a theoretical sense, have to be constructive.

Pandemic, Politics, Cancel Culture, and Love

Scott says the failure of institutions like the CDC and much of the media during COVID was staggering. He notes that the film Contagion got much right but could not imagine that incompetence and conspiracy thinking would be running things instead of fighting them. He favored human challenge trials and a World War II mentality, since each month a vaccine arrives sooner is worth trillions of dollars and many lives, calling the response "one of the biggest failures in the 240 year history of the United States." He admits he is terrified of a contested election and possible violence. Lex urges patience and love in November no matter who wins.

On cancel culture, Scott says he has defended unpopular people and ideas on his blog and been called racist and sexist for it. He refuses to let one faction define what those terms mean, and thinks the cancellation mentality is spectacularly ineffective at its own stated goals. He admires how Steven Pinker withstands attacks and wishes he could too; his own impulse is to engage every critic. His hope is that the large silent support for open discourse becomes less silent. Asked about love, he says he loves his kids, wife, and parents like most people, and recalls an XKCD cartoon in which every mathematical operation on a heart fails: "my normal approach is useless here."

Conclusion

This conversation shows Scott Aaronson doing what he does best: taking big, seductive ideas (simulated universes, measurable consciousness, quantum minds, chatbots that "think") and asking what they would actually require. His method is consistent: test theories on cases where we already know the answer, be honest about stacked speculations, and respect how far a simple universal mechanism can go, whether it's NAND gates or a word predictor trained on the internet. The complexity section makes P versus NP concrete by showing what a fast algorithm would unlock, and why he bets heavily against it. The final stretch turns human: frustration at failed institutions, fear for a divided country, a plea for open discourse, and a gentle admission that for love, math has no method. Lex closes with the line he borrowed from Scott at the start: "if you always win, then you're probably doing something wrong."

This is a summary of "#130 – Scott Aaronson: Computational Complexity and Consciousness" from Lex Fridman Podcast, giving you the GIST so you can decide if you want the REST. Listen to the full episode.