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.

✓ 2 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

P, NP, coNP, and Polynomial Reductions: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples keep the class containments concrete. One easy parity language already sits in $P$ , hence in both $N P$ and $c o N P$ ; another turns the abstract $N P \subseteq P S P A C E$ proof into an explicit lexicographic certificate search; and the counterexample shows why "NP" cannot mean "not polynomial."

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-09-02Open item page →

An even-length language sits in P, hence also in NP and coNP

Example

Let $E : = {x \in {0, 1}^{*} : ∣ x ∣ is even} .$ Then $E \in P$ , so $E \in N P \cap c o N P$ .

Facts & Assumptions

Given: The even-length language $E$ .

[L1]

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

Verification

technique · direct

1.1givenconstruct

A deterministic machine can decide $E$ by scanning the input once and toggling one parity bit in its finite control. At the end it accepts exactly when the parity is even. This runs in linear time, so $E \in P$ .

2.1L1step 1.1∎

Applying [L1] to step 1.1 gives $E \in N P \cap c o N P$ .

ExampleConstruction: AI-adaptedVerification: AI-generatedverified 2026-09-26 (gpt-6-sol)Open item page →

Lexicographic certificate search uses polynomial space and exponential time

Example

Suppose a language $L$ has a polynomial-time verifier whose certificates have length at most $n^{k}$ . A deterministic search through those certificates illustrates why the containment $N P \subseteq P S P A C E$ can hold even though the resulting algorithm may still take exponential time.

Facts & Assumptions

Given: A polynomial-time verifier with certificate length bound $n^{k}$ .

[L1]

The verifier search problem asks for a certificate witnessing acceptance, by The search problem attached to an NP verifier.

[L2]

Every language in $N P$ lies in $P S P A C E$ , and every language in $P S P A C E$ lies in $E X P$ , by $N P \subseteq P S P A C E \subseteq E X P$ .

Verification

technique · direct

1.1L1L2givenconstruct

Enumerate all binary certificates of lengths at most $n^{k}$ in lexicographic order and run the verifier on each until one succeeds. At every stage the algorithm stores only the input, the current certificate, and the verifier workspace. The verifier's polynomial time bound also bounds its visited workspace polynomially, so the total space usage is polynomial. This is the concrete mechanism behind the first inclusion in [L2].

2.1L2step 1.1∎

There are fewer than $2^{n^{k} + 1}$ candidate certificates, and the same procedure may test exponentially many of them before success or exhaustion. Its running time can therefore be exponential even while its space stays polynomial. That is exactly the gap displayed by the chain in [L2].

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-09-02Open item page →

A regular parity language refutes 'NP means not polynomial'

Statement refuted

The claim "NP means not polynomial-time solvable" is false. The even-length language already gives a counterexample.

Facts & Assumptions

Given: The language $E = {x \in {0, 1}^{*} : ∣ x ∣ is even}$ .

[L1]

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

[L2]

The false slogan being refuted is the one recorded in FALSE: NP means not polynomial-time solvable.

Counterexample

technique · direct

1.1givenconstruct

A one-pass parity scan decides $E$ in linear time, so $E \in P$ .

2.1L1L2step 1.1∎

By [L1], step 1.1 implies $E \in N P$ as well. Therefore [L2] is false: this NP-language is already polynomial-time solvable.

P, NP, coNP, and Polynomial Reductions: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

An even-length language sits in P, hence also in NP and coNP

Example

Facts & Assumptions

Verification

Lexicographic certificate search uses polynomial space and exponential time

Example

Facts & Assumptions

Verification

A regular parity language refutes 'NP means not polynomial'

Statement refuted

Facts & Assumptions

Counterexample

Sources