[#P39] P versus NP

Problem. The complexity classes \(\mathsf{P}\) and \(\mathsf{NP}\) are equal. Equivalently, every decision problem with polynomial-time verifiable yes-certificates has a deterministic polynomial-time decision algorithm.

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

The question asks whether efficient verification always implies efficient deterministic solution.

2Problem setup

Definition 1 (P). P is the class of decision problems decidable by a deterministic Turing machine in polynomial time.

Definition 2 (NP). NP is the class of decision problems whose yes-instances admit certificates verifiable by a deterministic Turing machine in polynomial time.

Remark 1. The question asks whether efficient verification always implies efficient deterministic solution.

3What counts as a solution

Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions.

1Status

What counts as a solution

Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: NP-completeness connects a polynomial-time algorithm for one NP-complete problem to all of NP. Strong lower bounds exist for restricted models, alongside formal barriers to several proof methods. Exact unresolved remainder: Determine whether every language in NP belongs to P, equivalently whether P=NP.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
Unresolved in this packet after the dated source check. Strongest checked result: NP-completeness connects a polynomial-time algorithm for one NP-complete problem to all of NP. Strong lower bounds exist for restricted models, alongside formal barriers to several proof methods. Exact unresolved remainder: Determine whether every language in NP belongs to P, equivalently whether P=NP.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 Unresolved in this packet after the dated source check. Strongest checked result: NP-completeness connects a polynomial-time algorithm for one NP-complete problem to all of NP. Strong lower bounds exist for restricted models, alongside formal barriers to several proof methods. Exact unresolved remainder: Determine whether every language in NP belongs to P, equivalently whether P=NP.^[1][2] Relevance to this problem For P versus NP, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: NP-completeness connects a polynomial-time algorithm for one NP-complete problem to all of NP. Strong lower bounds exist for restricted models, alongside formal barriers to several proof methods. Exact unresolved remainder: Determine whether every language in NP belongs to P, equivalently whether P=NP. Open full record →
Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions.^[1] Relevance to this problem For P versus NP, record p-versus-np-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Prove P = NP by giving a polynomial-time deterministic algorithm for an NP-complete problem and proving its running time and correctness, or prove P differs from NP within the standard formal definitions. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

Notes and companion material

Original intake status. The cited authoritative source listed this problem as unsolved when checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.

Consult the cited official problem description for the precise machine model, reductions, and prize conditions.

Recorded example 1. Boolean satisfiability is NP-complete, so a proven polynomial-time deterministic algorithm for it would prove P = NP.

2See also

Complexity of equality for binary-code weight enumeratorscomputational complexity
Winner complexity of Node Kayles on subcubic treescomputational complexity
Unique Games conjecturecomputational complexity

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“P versus NP.” TheoremDB. P39. Problem statement; statement text SHA-256 07db570f51b4de83e6eabdec58b4280091ce068c840b8a9c60aba625c39f0e6c. https://theoremdb.org/statement/?ref=P39

BibTeX

@misc{theoremdb-problem-07db570f51b4de83e6eabdec58b4280091ce068c840b8a9c60aba625c39f0e6c,
  title = {{P versus NP}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 07db570f51b4de83e6eabdec58b4280091ce068c840b8a9c60aba625c39f0e6c},
  url = {https://theoremdb.org/statement/?ref=P39}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from claymath.org^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. Clay Mathematics Institute, P vs NP, official Millennium Prize Problem page, checked 2026-08-01. Official Problem Description by Stephen Cook; listed under Unsolved Millennium Prize Problems. ↗website · primary source · checked 2026-07-31Source use: original summary.The cited authoritative source listed this problem as unsolved when checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Unsolved label and official overview.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Provides the authoritative current status and links Cook's official problem description.Source named by the research packet.
Stephen Cook, The P versus NP Problem, official Clay Mathematics Institute problem description. claymath.org checked 2026-08-01. Official problem description. ↗website · primary source · checked 2026-08-01Source use: original summary.Defines the target and foundational known results.

An original CC0 restatement prepared by TheoremDB maintainers.

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance