Prove that subset sum is NP-complete by reducing the existing 3-SAT language, to it. Given a list of positive integers and a nonnegative target, decide whether some selection of entries sums exactly to the target. Integers are encoded in binary.
theorem SubsetSumNP.subsetSum_npComplete :
CookLevin.NPComplete SubsetSumNP.SUBSET_SUM := by sorryThe binary-encoded SUBSET SUM language is NP-complete in the existing Cook–Levin model: it has a polynomial-time verifier with polynomially bounded accepted certificates, and every language in that NP class polynomial-time many-one reduces to it. Input entries are positive integers, repetitions are allowed as separate indexed choices, and the target is nonnegative.
The intended proof directly reduces KSat.KSAT 3 using the standard digit construction. The k-SAT goal specialized to 3 is the planned NP-hardness prerequisite. Implement the reduction and verifier on WordRAM and reuse the proved polynomial backend. Large encoded integers may occupy multiple machine words, so their construction and arithmetic must have polynomial step bounds in bit length. The formal conclusion is unconditional and does not prescribe a particular reduction or assume an unproved prerequisite as a hypothesis.
No open leaves. Every sub-goal is proved or awaiting decomposition.