Open
Unresolved assertion in the cited scope ↗
Stephen Cook · The P versus NP problem · Definition 2 and problem statement, pp. 2–3 →
Observed Oct 10, 2026
Conjecture · version 1
P = NP
Earlier version 1. View current version 2 →
Statement
Every language in NP is decidable by a deterministic polynomial-time algorithm.
Assumptions
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope
The affirmative answer to the canonical question.
Evidence
Source reports
Connections
In this problem · publication v3 · Selected context
P versus NP →
Primary formulation · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Equivalent statements
equivalent to ↕SAT in polynomial time
SAT is an equivalent decision target: a deterministic polynomial-time SAT algorithm establishes P = NP.
The equivalence is established; both target assertions remain unresolved.
Details & sources
P = NP →
Open · version 1
Every language in NP is decidable by a deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The affirmative answer to the canonical question.
SAT in polynomial time →
Open · version 1
Boolean satisfiability has a uniform deterministic polynomial-time decision algorithm.
- Boolean formula encoding; input length includes the formula.
Scope: The SAT decision target; presently unresolved.
SAT captures P versus NP →
Relationship statement · Proved · version 1
P = NP if and only if SAT is in P.
- Polynomial-time many-one reductions; SAT is NP-complete.
Scope: An established equivalence between two unresolved assertions.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v7
P versus NP →
Primary formulation · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Equivalent statements
equivalent to ↕SAT in polynomial time
SAT is an equivalent decision target: a deterministic polynomial-time SAT algorithm establishes P = NP.
The equivalence is established; both target assertions remain unresolved.
Details & sources
P = NP →
Open · version 1
Every language in NP is decidable by a deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The affirmative answer to the canonical question.
SAT in polynomial time →
Open · version 1
Boolean satisfiability has a uniform deterministic polynomial-time decision algorithm.
- Boolean formula encoding; input length includes the formula.
Scope: The SAT decision target; presently unresolved.
SAT captures P versus NP →
Relationship statement · Proved · version 1
P = NP if and only if SAT is in P.
- Polynomial-time many-one reductions; SAT is NP-complete.
Scope: An established equivalence between two unresolved assertions.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Stephen Cook · The P versus NP problem →
- Definition 2 and problem statement, pp. 2–3 → · Original passage ↗
Recorded wording
Every language in NP is decidable by a deterministic polynomial-time algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- Proposition 1(c) and SAT NP-completeness discussion, p. 5 → · Original passage ↗
Recorded wording
Boolean satisfiability has a uniform deterministic polynomial-time decision algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- Definition 4, Proposition 1(c) and SAT NP-completeness discussion, pp. 4–5 → · Original passage ↗
Recorded wording
P = NP if and only if SAT is in P.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Stephen Cook · Published
Published author exposition or original paper.
Stephen Cook · The P versus NP problem — proof text ↗Manuscript / exposition · external
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.
Stephen Cook · The P versus NP problem — proof text: official-description-sha256-018f3d473d16. 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.
Open
Unresolved assertion in the cited scope ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-equality
- Statement version
- 1
- SHA-256
- 1d1520f285735b048565aa97f1d933e70d077e6ab227feaaeefda9d98eca50de