Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026
Theorem · version 2
The natural-proofs barrier is conditional
Statement
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.
Assumptions
- Constructivity: the property is decidable in time polynomial in the truth-table length.
- Largeness: at least a 2^{-O(n)} fraction of n-input Boolean functions has the property.
- Usefulness against polynomial-size general Boolean circuits; the stated strong generator premise. H(G_k) is the least S permitting a size-at-most-S circuit to distinguish generator output from uniform with advantage greater than 1/S.
Scope
A conditional barrier for this precise kind of circuit-lower-bound method; not for all mathematical proofs.
Evidence
Source reports
Connections
In this problem · publication v11 · Selected context
P versus NP →
Proof barrier · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Scope: The natural-proofs barrier is conditional.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v14
P versus NP →
Proof barrier · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Scope: The natural-proofs barrier is conditional.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Razborov–Rudich · Natural proofs →
- §2.2 (natural properties), p. 7; hardness definition and Theorem 4.1, p. 15 → · Original passage ↗
Recorded wording
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.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Alexander Razborov · Steven Rudich · Published · Publication date 1994
Published author exposition or original paper.
Razborov–Rudich · Natural proofs — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: STOC-1994-author-paper. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Razborov–Rudich · Natural proofs — proof text: STOC-1994-author-paper. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-natural-proofs
- Statement version
- 2
- SHA-256
- 305260f62ba236fd3de39124e920d01766bd05a3d72e60453224b9f9c0087778