Proved
Established implication or scoped theorem in cited mathematics ↗
Stephen Cook · The P versus NP problem · Definition 4 and Proposition 1(c), pp. 4–5 →
Observed Oct 10, 2026
Theorem · version 2
If P ≠ NP, NP-complete problems have no polynomial algorithm
Statement
If P ≠ NP, every NP-complete decision language is outside P.
Assumptions
- Polynomial-time many-one NP-completeness; worst-case classical deterministic computation.
Scope
Rules out uniform polynomial-time algorithms, not efficient restricted-instance methods or heuristics.
Evidence
Source reports
Connections
In this problem · publication v14 · 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 follows from the definition of NP-completeness under the separation premise.
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
Stephen Cook · The P versus NP problem →
- Definition 4 and Proposition 1(c), pp. 4–5 → · Original passage ↗
Recorded wording
If P ≠ NP, every NP-complete decision language is outside 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.
Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-np-complete-hard
- Statement version
- 2
- SHA-256
- 5c2fee97380159d04e3c5d1e85e13cfbc0ea345e76e723e5afedd85a685ccbdb