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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Three States and the Proof Paradox in the Subset Sum Decision Problem

Zhenghan Xia
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Three States and the Proof Paradox in the Subset Sum Decision Problem

Zhenghan Xia
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon