Three States and the Proof Paradox in the Subset Sum Decision Problem
This paper proves a one-to-one correspondence between selections in standard positive-integer Subset Sum and solutions of a multivariable linear equation with a separate value restriction at each position. After partitioning by the number of selected items, deciding whether the original instance has a solution is equivalent to deciding whether at least one equation in the resulting family has a solution. We give the admissible range of selection sizes, count the candidates that remain after restriction, and state conditions for preserving solutions when positions are deleted. We use instances with opposite answers to show that specified grouping summaries and fixed congruence conditions can fail even when used together. We also give a necessary and sufficient condition for a set of candidates to occur together in a single solution and explain when a derivation becomes circular. When the only basis for a decision is the common structure of the problem, we rule out exact decision on grounds of correctness.
Authors
- Zhenghan Xia
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24429712
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint