Return to Revisions

The dichotomy between structure and randomness is one such theme. Tao's paper focuses on additive number theory, where the idea is that almost all sets are either highly structured (e.g., contain arithmetic progressions) or similar to a random set. But similar themes appear in computational complexity theory; low computational complexity is associated with structure, and high computational complexity is associated with randomness. Razborov and Rudich's result on natural proofs can loosely be thought of as an argument that certain kinds of simple proofs of P≠NP are highly unlikely because they would imply the existence of a lot more structure in randomness than most people expect there to be.