Reading source record STOC-1994-author-paper. View default cited record →
The precise statements and locators cited in this P versus NP research record.
Published author exposition or original paper.
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
If a polynomial-size pseudorandom generator G_k: {0,1}^k → {0,1}^{2k} has hardness H(G_k) ≥ 2^{k^ε} for some fixed ε > 0 and all sufficiently large k, then no P-natural property useful against P/poly exists.
Passage ID: pnp-entry-natural-proofs:v1
Source item: natural-proofs
Source record: pnp-rr@STOC-1994-author-paper
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v14
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
A conditional barrier for this precise kind of circuit-lower-bound method; not for all mathematical proofs.
Observed Oct 10, 2026
History
Natural proofs connect lower bounds to pseudorandomness
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: STOC-1994-author-paper
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
493cd619b123213f23de32f5075f34d30c563cbd562e025c99b0207568bc1c58Recorded authorship
Alexander Razborov · Steven Rudich
Alexander Razborov; Steven Rudich
AI involvement is not reported by this cited source; this is not a claim of its absence.
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
Razborov–Rudich · Natural proofs
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗