# P39: P versus NP

- ID: `P39`
- Reference: `p-versus-np`
- Page: https://theoremdb.org/statements/P39
- Record maturity: Reviewed problem with recorded work

## 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.

### Context

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

### Problem setup

- **Definition (P).** P is the class of decision problems decidable by a deterministic Turing machine in polynomial time.
- **Definition (NP).** NP is the class of decision problems whose yes-instances admit certificates verifiable by a deterministic Turing machine in polynomial time.
- **Remark.** The question asks whether efficient verification always implies efficient deterministic solution.

### What 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.

## Status

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](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- Original intake status: 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.
- Status and formulation were checked against the Clay Mathematics Institute page on 2026-07-22.
- Consult the cited official problem description for the precise machine model, reductions, and prize conditions.

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

### Open directions

- **Route 1** (reported): 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](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `p-versus-np`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://www.claymath.org/millennium/p-vs-np/
   - Also cited at Unsolved label and official overview
   - Also cited at Editorial research route recorded 2026-07-31
   - website; primary source; checked 2026-07-31
   - Source 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.
   - 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.
2. <a id="reference-2"></a>Stephen Cook, The P versus NP Problem, official Clay Mathematics Institute problem description. claymath.org checked 2026-08-01. Official problem description https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
   - website; primary source; checked 2026-08-01
   - Source use: original_summary
   - Defines the target and foundational known results.