The precise statements and locators cited in this P versus NP research record.
Published author exposition or original paper.
7 cited passages ↓1 problem ↓Record official-description-sha256-018f3d473d16 ↓
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
Every language in NP is decidable by a deterministic polynomial-time algorithm.
Passage ID: pnp-entry-equality:v1
Source item: equality
Source record: pnp-cook@official-description-sha256-018f3d473d16
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
Passage ID: pnp-entry-inequality:v1
Source item: inequality
Source record: pnp-cook@official-description-sha256-018f3d473d16
If P ≠ NP, every NP-complete decision language is outside P.
Passage ID: pnp-entry-np-complete-hard:v1
Source item: np-complete-hard
Source record: pnp-cook@official-description-sha256-018f3d473d16
NP and coNP are distinct.
Passage ID: pnp-entry-np-conp:v1
Source item: np-conp
Source record: pnp-cook@official-description-sha256-018f3d473d16
If P = NP, then every polynomially balanced, polynomial-time-decidable witness relation admits polynomial-time witness search or correct reporting that no witness exists.
Passage ID: pnp-entry-np-search:v1
Source item: np-search
Source record: pnp-cook@official-description-sha256-018f3d473d16
P = NP if and only if SAT is in P.
Passage ID: pnp-entry-sat-equivalence:v1
Source item: sat-equivalence
Source record: pnp-cook@official-description-sha256-018f3d473d16
Boolean satisfiability has a uniform deterministic polynomial-time decision algorithm.
Passage ID: pnp-entry-sat-in-p:v1
Source item: sat-in-p
Source record: pnp-cook@official-description-sha256-018f3d473d16
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v14
Source assessment
Open
Unresolved assertion in the cited scope
The affirmative answer to the canonical question.
Observed Oct 10, 2026
Source assessment
Open
Unresolved assertion in the cited scope
The conjectural negative answer to the same canonical question.
Observed Oct 10, 2026
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
Rules out uniform polynomial-time algorithms, not efficient restricted-instance methods or heuristics.
Observed Oct 10, 2026
Source assessment
Open
Unresolved assertion in the cited scope
A stronger related separation; not equivalent to P ≠ NP.
Observed Oct 10, 2026
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
An asymptotic search consequence for these relations; output length and encoding restrictions matter.
Observed Oct 10, 2026
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
An established equivalence between two unresolved assertions.
Observed Oct 10, 2026
Connection
SAT is an equivalent decision target: a deterministic polynomial-time SAT algorithm establishes P = NP.
Source assessment
Open
Unresolved assertion in the cited scope
The SAT decision target; presently unresolved.
Observed Oct 10, 2026
Definition
Decision problem and certificate
Question
P versus NP
Further reading
Read the setting and notation before comparing the results.
History
NP-completeness gives a common target
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: official-description-sha256-018f3d473d16
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
018f3d473d16c35e807e8cdfbd0bed3ccf7a56452e3e10c6b1d84b56eaf2cf59Recorded authorship
Stephen Cook
AI involvement is not reported by this cited source; this is not a claim of its absence.
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
Stephen Cook · The P versus NP problem
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗