Proved
Established implication or scoped theorem in cited mathematics ↗
Avi Wigderson · Mathematics and Computation · Theorem 5.5 [KL82], §5.2.1 →
Observed Oct 10, 2026
Theorem · version 1
Polynomial NP circuits would collapse the hierarchy
Earlier version 1. View current version 2 →
Statement
If NP is contained in P/poly, then PH = Σ₂^P.
Assumptions
- Nonuniform polynomial-size Boolean circuits for NP; the classical polynomial hierarchy.
Scope
The Karp–Lipton implication; the circuit containment premise remains unresolved.
Evidence
Source reports
Connections
In this problem · publication v6 · 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.
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 v7
P versus NP →
Conditional implication · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
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
Avi Wigderson · Mathematics and Computation →
- Theorem 5.5 [KL82], §5.2.1 → · Original passage ↗
Recorded wording
If NP is contained in P/poly, then PH = Σ₂^P.
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.
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-karp-lipton
- Statement version
- 1
- SHA-256
- d66fa8d2ee17e480325be3bfc7fd87e8d1e7cf1c714fd70ba55f9e0120b41913