A card from a free library — ask anything, no account, works offline. Every card carries its source.
Razborov 1997 — Natural proofs
chain
A. A. Razborov, S. Rudich (1997). Natural proofs. J. Comput. System Sci. 55 (1997) 24–35. DOI 10.1006/jcss.1997.1494. Canonical: https://doi.org/10.1006/jcss.1997.1494. Cited by its record. License as found: Elsevier open archive user license — free to read. What it gave the chain: the second barrier: natural proofs cannot, if one-way functions exist.
source
card id
card_chain_razborov_rudich_1997
address
WIT.codex.FCT/natural-proofs/REF.WITNESSED@a-a-razborov-s-rudich
adjoining cards
- builds on → Baker 1975 — Relativizations of the P =? NP question — the second barrier: natural proofs cannot, if one-way functions exist
- enables → Aaronson 2009 — Algebrization: a new barrier in complexity theory — the third barrier: algebrizing proofs cannot
Is this card incomplete? Tell the library — it will call out for more ↗