PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An NP-complete language in P forces $P = N P$

Statement

If some NP-complete language belongs to $P$ , then $P = N P$ .

Facts & Assumptions

Given: An NP-complete language $C$ with $C \in P$ .

[L1]

NP-complete means both $C \in N P$ and every language in $N P$ reduces to $C$ in polynomial time, by NP-hard and NP-complete languages.

[L2]

Polynomial-time many-one reductions transfer $P$ -membership backward: if $A \leq_{p} B$ and $B \in P$ , then $A \in P$ , by Polynomial-time many-one reductions transfer P-, NP-, and coNP-membership.

[L3]

Every language in $P$ belongs to $N P$ , by $P \subseteq N P \cap c o N P$ .

Proof

technique · direct

1.1

Let $L \in N P$ be arbitrary. By [L1], because $C$ is NP-hard, there is a polynomial-time many-one reduction $L \leq_{p} C$ . Then [L2] and the hypothesis $C \in P$ give $L \in P$ .

L1L2given

2.1

Step 1.1 shows $N P \subseteq P$ . By [L3], every language in $P$ also lies in $N P$ , so $P \subseteq N P$ . Therefore $P = N P$ .

L3step 1.1∎

Depends on

Used by

FALSE: NP-complete means proven not to lie in P False statement

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Stephen A. Cook, The Complexity of Theorem-Proving Procedures (standard reference, not scraped)
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)

An NP-complete language in P forces P=NPP=NP