Proved
Established implication or scoped theorem in cited mathematics ↗
Avi Wigderson · Mathematics and Computation · §5.2.1, Theorem 5.3 →
Observed Oct 10, 2026
Theorem · version 2
General NP circuit lower bounds would separate P and NP
Statement
If NP is not contained in P/poly, then P ≠ NP.
Assumptions
- Uniform polynomial-time algorithms have polynomial-size nonuniform circuits.
Scope
A one-direction sufficient condition; the converse is not established.
Evidence
Source reports
Connections
In this problem · publication v12 · Selected context
P versus NP →
Conditional implication · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
General NP circuit lower bounds suffice for separation; the reverse is not asserted.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
One-way implication
Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.
The reverse implication is not established; restricted gates or larger target classes do not satisfy this premise.
Details & sources
NP lacks polynomial-size general circuits →
Open · version 2
NP is not contained in P/poly.
- Nonuniform families of polynomial-size unrestricted Boolean circuits.
Scope: A stronger circuit-complexity target than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
General NP circuit lower bounds would separate P and NP →
Relationship statement · Proved · version 2
If NP is not contained in P/poly, then P ≠ NP.
- Uniform polynomial-time algorithms have polynomial-size nonuniform circuits.
Scope: A one-direction sufficient condition; the converse is not established.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v14
P versus NP →
Conditional implication · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
General NP circuit lower bounds suffice for separation; the reverse is not asserted.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
One-way implication
Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.
The reverse implication is not established; restricted gates or larger target classes do not satisfy this premise.
Details & sources
NP lacks polynomial-size general circuits →
Open · version 2
NP is not contained in P/poly.
- Nonuniform families of polynomial-size unrestricted Boolean circuits.
Scope: A stronger circuit-complexity target than P ≠ NP.
P ≠ NP →
Open · version 3
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
General NP circuit lower bounds would separate P and NP →
Relationship statement · Proved · version 2
If NP is not contained in P/poly, then P ≠ NP.
- Uniform polynomial-time algorithms have polynomial-size nonuniform circuits.
Scope: A one-direction sufficient condition; the converse is not established.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Avi Wigderson · Mathematics and Computation →
- §5.2.1, Theorem 5.3 → · Original passage ↗
Recorded wording
If NP is not contained in P/poly, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §5.2.1, Theorem 5.3 and Conjecture 5.4 → · Original passage ↗
Recorded wording
NP is not contained in P/poly.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Avi Wigderson · Published · Publication date 2019
Published author exposition or original paper.
Avi Wigderson · Mathematics and Computation — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: author-draft-2019-08-06. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Avi Wigderson · Mathematics and Computation — proof text: author-draft-2019-08-06. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Stephen Cook · The P versus NP problem →
- Problem statement and discussion, pp. 2–3 → · Original passage ↗
Recorded wording
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Stephen Cook · Published
Published author exposition or original paper.
Revision & attribution
Source revision: official-description-sha256-018f3d473d16. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
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-circuits-imply-separation
- Statement version
- 2
- SHA-256
- eb6e53bad7ea91d711eb4bcca644c67d8f4b9e60206920488bb42549f72970ac