CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 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.

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

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

givenconstruct

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

L1L2step 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

Michael Sipser, MIT 18.404J Theory of Computation, Lecture 14: P and NP, SAT, Poly-time Reducibility (standard reference, not scraped)