PropositionStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Np and conp are the first levels

Statement

$Σ_{1}^{p} = N P$ and $Π_{1}^{p} = c o N P$ .

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

First-level existential and universal polynomial-time predicates define the first hierarchy levels. (Polynomial hierarchy levels).

[F2]

NP consists of languages admitting polynomial-time verifiers with polynomially bounded certificates. (The class NP via polynomial-time verifiers).

[F3]

coNP consists of complements of NP languages in the same binary-string universe. (The class coNP).

Proof

1.1

A first-level existential predicate is a polynomial-time verifier with a polynomial-length certificate, so it defines an NP language. Conversely, encode a bounded-length verifier certificate by a length field and padding; a total decoding onto all allowed certificates preserves existence and gives the first-level predicate. This includes length zero and the empty input.

F1F2

2.1

Negating that existential formula yields a universal formula for the complement. Conversely negating a universal formula yields an NP verifier. By the definition of coNP these are exactly the languages of $Π_{1}^{p}$ .

F3step 1.1∎

Depends on

Used by

Np and conp are the first levels Example
Elementary high low identities Proposition
Quantifier and oracle characterizations of ph Theorem

Dependency tree · two levels

5 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

Arora–Barak, Computational Complexity, 2007 draft; §5.2 Remark5.5, p92. (standard reference, not scraped)