"The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks,

"The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They're a great way to illustrate the point, they were probably essential for discovering the point, but they're not the point. The best definition of complexity theory I can think of is that it's quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods. Its concerns include: If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.) Which gods are mightier than which other gods? (PNP vs. PP, SZK vs. QMA, BQPNP vs. NPBQP, etc. etc.) Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.) Can oracles be trusted? (Can oracles be trusted?) And of course: Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)" https://www.scottaaronson.com/blog/?p=56 https://www.scottaaronson.com/blog/?p=56