AI, Quantum Computing, and Beyond

Building on his earlier introduction to the P vs. NP problem, Tim Roughgarden dives into the deeper consequences of this open question. He examines NP-intermediate problems like factoring and graph isomorphism, which sit awkwardly between easy and hard, and explains why these cases matter for encryption and network analysis. Roughgarden then considers three possible futures: What if P does not equal NP? What if it does, with fast algorithms? And what if it does, but only in a useless theoretical sense? Each scenario carries radically different implications. The lecture then turns to whether new technologies can sidestep classical limits. Quantum computers appear genuinely capable of solving certain problems, like factoring via Shor's algorithm, far more efficiently than classical computers, prompting a revision of the Extended Church-Turing Thesis and a race toward post-quantum cryptography. But AI, despite appearances, does not overcome fundamental computational barriers. Roughgarden closes with a striking claim: computation's deepest truths transcend any particular technology, offering a kind of permanence in a rapidly changing world.