§5.2.1, Theorem 5.3
If NP is not contained in P/poly, then P ≠ NP.
Passage details
Passage ID: pnp-entry-circuits-imply-separation:v1
Source item: circuits-imply-separation
Source record: pnp-book@author-draft-2019-08-06
Avi Wigderson · Mathematics and Computation
PublishedPublication date 2019
Open paper ↗Reading source record author-draft-2019-08-06. View default cited record →
Overview
The precise statements and locators cited in this P versus NP research record.
Published author exposition or original paper.
9 cited passages ↓1 problem ↓Record author-draft-2019-08-06 ↓
Passages
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
Passage index · 9
§3.5, NP versus coNP
If NP ≠ coNP, then P ≠ NP.
Passage details
Passage ID: pnp-entry-conp-implies-separation:v1
Source item: conp-implies-separation
Source record: pnp-book@author-draft-2019-08-06
§4.1, polynomial hierarchy; P = NP collapse discussion
If P = NP, then PH = P.
Passage details
Passage ID: pnp-entry-hierarchy-collapse:v1
Source item: hierarchy-collapse
Source record: pnp-book@author-draft-2019-08-06
Theorem 5.5 [KL82], §5.2.1
If NP is contained in P/poly, then PH = Σ₂^P.
Passage details
Passage ID: pnp-entry-karp-lipton:v1
Source item: karp-lipton
Source record: pnp-book@author-draft-2019-08-06
Theorem 4.1 [Lad75], §4.2
If P ≠ NP, then some languages in NP are neither in P nor NP-complete under polynomial-time many-one reductions.
Passage details
Passage ID: pnp-entry-ladner:v1
Source item: ladner
Source record: pnp-book@author-draft-2019-08-06
§5.2.1, Theorem 5.3 and Conjecture 5.4
NP is not contained in P/poly.
Passage details
Passage ID: pnp-entry-np-circuits:v1
Source item: np-circuits
Source record: pnp-book@author-draft-2019-08-06
Definition 4.7 and §4.5
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
Passage details
Passage ID: pnp-entry-one-way:v1
Source item: one-way
Source record: pnp-book@author-draft-2019-08-06
§4.4–4.5, Definition 4.7 and discussion
If standard one-way functions exist, then P ≠ NP.
Passage details
Passage ID: pnp-entry-owf-implies-separation:v1
Source item: owf-implies-separation
Source record: pnp-book@author-draft-2019-08-06
§12.4, algebraic reductions and completeness
Over a field of characteristic zero, VP and VNP are distinct.
Passage details
Passage ID: pnp-entry-vp-vnp:v1
Source item: vp-vnp
Source record: pnp-book@author-draft-2019-08-06
Used in
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
P versus NP →
Problem publication v14
General NP circuit lower bounds would separate P and NP →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
A one-direction sufficient condition; the converse is not established.
Observed Oct 10, 2026
Connection
Nonuniform general NP circuit lower bounds would suffice for P ≠ NP.
NP versus coNP would separate P and NP →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
The implication does not establish its premise.
Observed Oct 10, 2026
Connection
Separating NP from coNP would also separate P from NP.
If P = NP, the polynomial hierarchy collapses to P →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
An asymptotic complexity-class consequence, not a practical algorithm implementation.
Observed Oct 10, 2026
Polynomial NP circuits would collapse the hierarchy →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
The Karp–Lipton implication; the circuit containment premise remains unresolved.
Observed Oct 10, 2026
If P ≠ NP, intermediate problems exist →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
Existence of NP-intermediate languages; not a classification of specific natural candidates.
Observed Oct 10, 2026
NP lacks polynomial-size general circuits →
Source assessment
Open
Unresolved assertion in the cited scope
A stronger circuit-complexity target than P ≠ NP.
Observed Oct 10, 2026
Standard one-way functions exist →
Source assessment
Open
Unresolved assertion in the cited scope
Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
Observed Oct 10, 2026
One-way functions would separate P and NP →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
The reverse implication is not established; P ≠ NP alone is not a security guarantee.
Observed Oct 10, 2026
Connection
Average-case one-wayness is a stronger sufficient hardness premise.
VP versus VNP →
Source assessment
Open
Unresolved assertion in the cited scope
An algebraic analogue; no equivalence to Boolean P versus NP is asserted.
Observed Oct 10, 2026
Problem context · 11 citations
Question
P versus NP
- §5.2.1, Theorem 5.3 ↑
- §3.5, NP versus coNP ↑
- §4.1, polynomial hierarchy; P = NP collapse discussion ↑
- Theorem 5.5 [KL82], §5.2.1 ↑
- Theorem 4.1 [Lad75], §4.2 ↑
- §5.2.1, Theorem 5.3 and Conjecture 5.4 ↑
- Definition 4.7 and §4.5 ↑
- §4.4–4.5, Definition 4.7 and discussion ↑
- §12.4, algebraic reductions and completeness ↑
Connection
VP versus VNP is an algebraic complexity analogue, with field operations and polynomial families.
Files
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Avi Wigderson · Mathematics and Computation — proof text ↗
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: author-draft-2019-08-06
File checksum
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
c6b72d0487d31b7d7173266c8d6706649607c6615defb7e2b6c2395782ab1829Credits
Recorded authorship
Avi Wigderson
AI involvement not reported
AI involvement is not reported by this cited source; this is not a claim of its absence.
Versions
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
- author-draft-2019-08-06 · selectedObserved Oct 10, 2026 · used in current publications
Avi Wigderson · Mathematics and Computation
Record details
- Source ID
- pnp-book
- Record ID
- pnp-book@author-draft-2019-08-06
- Recorded title
- Avi Wigderson · Mathematics and Computation
- Revision
- author-draft-2019-08-06
- Observed
- Oct 10, 2026
- Source updated
- Not recorded
- Content SHA-256
- c6b72d0487d31b7d7173266c8d6706649607c6615defb7e2b6c2395782ab1829
- Update method
- Manual primary-source check; changes require a new source version and staff publication.
- Identifier policy
- Source URL and exact theorem/section locator; no inferred identity merge.
- Check interval
- 30 days
- Rights
- metadata-link
- License
- Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗