DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-05

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.

Subset sum and partition decision problems

Definition

An instance of SUBSET SUM is a finite list of positive integers $a_{1}, \dots, a_{n}$ written in binary together with a target integer $d > 0$ , also written in binary. It is a yes-instance when some subset of the listed integers sums exactly to $d$ .

An instance of PARTITION is a finite list of positive integers $q_{1}, \dots, q_{r}$ written in binary. It is a yes-instance when the list can be divided into two subcollections having the same total sum.

Used by

A pseudopolynomial algorithm is polynomial in the binary input length False statement
3SAT polynomial-time many-one reduces to subset sum Theorem
Subset sum polynomial-time many-one reduces to partition Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Fabrizio Iozzi and Luca Trevisan, Handout NP2 (standard reference, not scraped)
Fabrizio Iozzi and Luca Trevisan, Handout NP3 (standard reference, not scraped)