TheoremStatement: Literature-sourcedProof: 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.

Polynomial-time many-one reductions transfer P-, NP-, and coNP-membership

Statement

Let $A, B \subseteq {0, 1}^{*}$ and suppose that $A \leq_{p} B$ .

If $B \in P$ , then $A \in P$ .
If $B \in N P$ , then $A \in N P$ .
If $B \in c o N P$ , then $A \in c o N P$ .

Facts & Assumptions

Given: Binary languages $A, B \subseteq {0, 1}^{*}$ and a fixed total polynomial-time map $f$ witnessing $A \leq_{p} B$ .

[L1]

A polynomial-time many-one reduction is a total polynomial-time membership-preserving map, by Polynomial-time many-one reductions.

[L2]

Composites of polynomial-time many-one reductions are again polynomial-time many-one reductions, by Polynomial-time many-one reductions compose.

[L3]

$P$ is the class of polynomial-time decidable languages, by The class P.

[L4]

$N P$ is the class of languages with polynomial-time verifiers and polynomially bounded certificates, by The class NP via polynomial-time verifiers and Polynomial-time verifiers with polynomially bounded certificates.

[L5]

$c o N P$ consists of complements of NP-languages, by The class coNP.

Proof

technique · direct

1.1L1L3givenconstruct

Assume $B \in P$ , and let $D_{B}$ be a polynomial-time decider for $B$ from [L3]. On input $x$ , compute the fixed map $f (x)$ and then run $D_{B}$ on that output. By [L1], the answer is correct because $x \in A$ iff $f (x) \in B$ , and the whole procedure is polynomial-time because both stages are. Thus $A \in P$ .

1.2L1L4givenconstruct

Assume $B \in N P$ . By [L4], choose a verifier relation $R_{B}$ and polynomial certificate bound $p$ for $B$ . Using the fixed reduction map $f$ , define a verifier for $A$ by declaring that $(x, u)$ is accepted exactly when $(f (x), u) \in R_{B}$ . The output length $∣ f (x) ∣$ is polynomial in $∣ x ∣$ , so the bound $p (∣ f (x) ∣)$ is still polynomial in $∣ x ∣$ . Correctness follows from $x \in A ⟺ f (x) \in B ⟺ \exists u with ∣ u ∣ \leq p (∣ f (x) ∣) and (f (x), u) \in R_{B}$ . Therefore $A \in N P$ .

2.1L1L2L5step 1.2given

Assume $B \in c o N P$ . Then $B^{c} \in N P$ by [L5]. The fixed reduction map $f$ also witnesses $A^{c} \leq_{p} B^{c}$ , because $x \in A^{c} ⟺ x \notin A ⟺ f (x) \notin B ⟺ f (x) \in B^{c}$ . Applying step 1.2 to the reduction $A^{c} \leq_{p} B^{c}$ gives $A^{c} \in N P$ , and then [L5] yields $A \in c o N P$ . The composition principle [L2] guarantees that chaining such transfers remains inside the same reduction class.

3.1step 1.1step 1.2step 2.1∎

Steps 1.1, 1.2, and 2.1 prove the three transfer clauses.

Depends on

Used by

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

Dependency tree · two levels

8 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)
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)