P vs NP, and randomness

Just a bookmark for myself

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

 While fascinating in its own right, cryptography seemed far removed from the self-referential arguments that had first drawn Rudich and Impagliazzo into the field. But as Rudich struggled to understand why the circuit complexity approach had stalled, he began to realize that the two subjects weren’t so far apart after all. The strategy researchers had adopted in their attempts to prove P ≠ NP had a self-defeating character reminiscent of Gödel’s famous proposition “this statement is unprovable” — and cryptography could help explain why. In Russia, Razborov discovered a similar connection around the same time. These were the seeds of the natural proofs barrier.

The tension at the heart of the natural proofs barrier is that the task of distinguishing high-complexity functions from low-complexity ones is similar to the task of distinguishing true randomness from the pseudorandomness used to encrypt messages. We’d like to show that high-complexity functions are categorically different from low-complexity functions, to prove P ≠ NP. But we’d also like for pseudorandomness to be indistinguishable from randomness, to be confident in the security of cryptography. Maybe we can’t have it both ways.