False statementConstruction: AI-adaptedVerification: 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.

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

Statement

If a language is NP-complete, then it has already been proved not to belong to $P$ .

Facts & Assumptions

Given: An NP-complete language $C$ .

[L1]

NP-complete means that $C$ lies in $N P$ and every NP-language reduces to it, by NP-hard and NP-complete languages.

[L2]

If an NP-complete language lies in $P$ , then $P = N P$ , by An NP-complete language in P forces $P = N P$ .

[F1]

The question whether $P = N P$ remains unsolved; the Clay Mathematics Institute lists P versus NP as an unsolved Millennium Prize Problem.

Refutation

technique · direct

1.1

The definition quoted in [L1] contains no clause asserting $C \notin P$ . It says only that $C$ is in $N P$ and is hard for $N P$ under the chosen reductions.

L1given

2.1

If $C \notin P$ had already been proved, then [L1] would give a language in $N P ∖ P$ and hence prove $P \neq N P$ . But [F1] records that this question remains unsolved. Conversely, [L2] says that finding $C \in P$ would prove $P = N P$ . Thus NP-completeness does not mean that exclusion from $P$ has already been proved; it identifies the consequence either kind of resolution would have.

L1L2F1step 1.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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)
Clay Mathematics Institute, P vs NP (standard reference, not scraped)