Subset Sum Instances in ZFC Limbo

2020/12/10 by S. Gill Williamson, Williamson, S. Gill
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2012.05385

arxiv created 2021/10/29 · arxiv updated 2021/11/01

Abstract

Our main result, Theorem 2.5, shows the existence of a vast infinity of subset sum problems solvable in polynomial time. The only proof we have of this result uses the ZFC independent Jump Free Theorem of Harvey Friedman, thus putting Theorem 2.5 in what we call ZFC limbo. The mathematics we use is elementary and at the level of a good undergraduate course in combinatorics or design and analysis of algorithms. The statement of the Jump Free Theorem is also easily understood at this level (but not the proof).

Related

• On the existence of polynomial-time algorithms to the subset sum problem
• ZFC independence and subset sum
• On the difficulty of proving P equals NP in ZFC
• The problematic nature of potentially polynomial-time algorithms solving the subset-sum problem
• Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide