openmath.dev
Esc

Loading…

↑ ↓ to move↵ to open

Appearance
Appearance

Theorem · version 2

If P = NP, NP witnesses can be found efficiently

Statement

If P = NP, then every polynomially balanced, polynomial-time-decidable witness relation admits polynomial-time witness search or correct reporting that no witness exists.

Assumptions

  • Polynomial witness length and checkable relation; binary encodings; prefix queries are languages in NP.

Scope

An asymptotic search consequence for these relations; output length and encoding restrictions matter.

Evidence

Connections

In this problem · publication v8 · 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 v14

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

Stephen Cook · The P versus NP problem →

  • Decision versus search discussion, p. 5 → · Original passage ↗
    Recorded wording

    If P = NP, then every polynomially balanced, polynomial-time-decidable witness relation admits polynomial-time witness search or correct reporting that no witness exists.

    paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.

Stephen Cook · Published

Published author exposition or original paper.

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.

Record details
Claim ID
claim-pnp-np-search
Statement version
2
SHA-256
6ab4a2b77402d9d7b24c929c269eaa2940c3689ad3139c59ab6c11fbe677247b

Publication records