False statementConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedverified 2026-09-26 (gpt-6-sol)

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.

Every decision many-one reduction is parsimonious

Statement

Every polynomial-time many-one reduction between decision problems preserves the exact number of witnesses.

Facts & Assumptions

Given: On binary inputs $w$ , let $f (w)$ count the sole witness $ε$ and let $g (w)$ count the two witnesses $0$ and $1$ . These are counting functions with $f (w) = 1$ and $g (w) = 2$ for every $w$ ; their associated decision languages, defined by positive count, are both ${0, 1}^{*}$ .

[L1]

A decision many-one reduction need preserve only membership, by Polynomial-time many-one reductions.

[L2]

A parsimonious reduction preserves exact counts, by Parsimonious reductions between counting functions.

Refutation

technique · direct

1.1L1givenconstruct

Let $r (w) = w$ for every binary word $w$ . This is a total linear-time map. The two positive-count decision languages are both ${0, 1}^{*}$ , so $r$ is a many-one reduction between them by [L1].

2.1L2givenstep 1.1

For every $w$ , the source has exactly one accepting witness $ε$ , whereas the target has exactly the two accepting witnesses $0, 1$ . Hence $f (w) = 1 \neq 2 = g (r (w))$ , so $r$ is not parsimonious under [L2]. Both witness relations are decidable in constant time once their witness is read.

3.1step 1.1step 2.1∎

This one polynomial-time decision reduction refutes the universal claim.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 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 and Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Lance Fortnow, Counting Complexity (standard reference, not scraped)