Natural proofs barrier
Statement
Razborov–Rudich (1997): Any "natural" proof that a function is hard for a circuit class would yield an efficient algorithm to break pseudorandom generators. Thus P≠NP cannot be proven with existing mathematical techniques that satisfy naturalness. Abacus (1990), Knuth (2021).
Formula
Natural proof ⇒ break PRG
Proof sketch
ZFC 9+1 → circuits, pseudorandomness. Natural proofs: constructive, large, useful. If all three hold, then PRGs do not exist. Most known lower-bound techniques are natural.
Source
Razborov & Rudich, JCSS 55 (1997). IMU Abacus 1990, Knuth Prize 2021.
Domains
computer-science