Computational Limits
Scott Aaronson's "What Google Won't Find" is the most honest popular account of computational complexity I've read, because it starts from the right place: explaining what we don't know, which is almost everything.
The P vs NP Landscape
The question P = NP? asks whether every problem whose solution can be efficiently verified can also be efficiently solved. Most computer scientists believe the answer is no — there are problems where checking an answer is easy but finding one is hard. But nobody can prove it. P vs NP has been open since 1971, and it's one of the Clay Mathematics Institute's million-dollar Millennium Problems.1
Aaronson's contribution to the popular understanding of this problem is to take it seriously as a scientific claim rather than a mathematical curiosity. If P = NP, the consequences would be staggering: every NP problem (scheduling, protein folding, circuit design, theorem proving) would be efficiently solvable. The entire architecture of modern cryptography-as-capability collapses, because the security of cryptographic systems depends on certain problems being hard. If factoring large numbers were in P, RSA is dead. If the discrete logarithm problem were in P, Diffie-Hellman and elliptic curve cryptography are dead.1
But Aaronson is careful to note the gap between "polynomial time" and "practical." Even if someone proved P = NP, the algorithm might have a polynomial exponent so large (n^1000000) that it would be useless in practice. And conversely, some NP-hard problems have excellent heuristic solvers that work well on real-world instances even though worst-case complexity is exponential. SAT solvers, for example, routinely handle instances with millions of variables that are "hard" in the worst case.
Quantum Computing's Real Promise
The section on quantum computing is where Aaronson, himself a quantum computing theorist, is most usefully contrarian. Quantum computers are not "exponentially faster than classical computers" for all problems. They inhabit their own complexity class (BQP — bounded-error quantum polynomial time) that sits somewhere between P and NP. Quantum computers can factor integers efficiently (Shor's algorithm) and search unstructured databases quadratically faster (Grover's algorithm), but there's no known quantum algorithm that efficiently solves NP-complete problems in general.1
The common misconception — that a quantum computer tries all answers simultaneously and picks the right one — is wrong in a specific and important way. A quantum computer does explore a superposition of states, but you can only extract information by measuring, which collapses the superposition. The art of quantum algorithm design is arranging the computation so that correct answers constructively interfere (their amplitudes add up) and incorrect answers destructively interfere (their amplitudes cancel out). This is possible for some problem structures but not others.
Aaronson's practical assessment: quantum computers will be transformative for quantum simulation (chemistry, materials science), useful for some optimization problems, and irrelevant for most everyday computation. They won't make search-and-indexing faster. They won't help you compile code. They will break most current public-key cryptography, which is why the migration to post-quantum algorithms is already underway — but that's a specific, contained threat with known countermeasures.
What Hardness Actually Means
The most philosophically interesting part of Aaronson's argument is about what the existence of hard problems tells us about the structure of reality. If P ≠ NP (as almost everyone believes), it means the universe contains mathematical structures that are easy to verify but hard to find. This is a fact about mathematics, not about computers. No matter how fast our hardware gets, the exponential wall doesn't move.
This has consequences for fields well beyond computer science. In machine learning, the training process is essentially search — finding parameters that fit data well. If the loss landscape has many local minima separated by high barriers, gradient descent will get stuck, and the problem is computationally hard in a P vs NP sense. In economics, finding market equilibria is PPAD-complete, which suggests that markets might not actually converge to equilibrium in any reasonable time. In biology, protein folding is NP-hard in the worst case, though AlphaFold's success on real proteins suggests that naturally evolved proteins might lie in an easy subclass.
The deepest question Aaronson raises: is the universe itself "computationally bounded"? If physical processes can be simulated on a computer (the Church-Turing thesis applied to physics), then the computational limits of algorithms are also limits on what physical systems can do. A brain is a physical system. If NP-hard problems are genuinely hard, then no amount of neural hardware will make them easy. Creativity, insight, mathematical genius — all must operate within the same computational limits as silicon, just with different constants.