On the existence of polynomial-time algorithms to the subset sum problem

2008/09/29 by Jormakka, Jorma
#FOS: Mathematics #General Mathematics (math.GM)

paper · doi:10.48550/arxiv.0809.4935

Abstract

This paper proves that there does not exist a polynomial-time algorithm to the the subset sum problem. As this problem is in NP, the result implies that the class P of problems admitting polynomial-time algorithms does not equal the class NP of problems admitting nondeterministic polynomial-time algorithms.

Related

• The problematic nature of potentially polynomial-time algorithms solving the subset-sum problem
• An Improved Pseudopolynomial Time Algorithm for Subset Sum
• A Polynomial-Time Algorithm for Special Cases of the Unbounded Subset-Sum Problem
• A novel and efficient algorithm to solve subset sum problem
• Does Subset Sum Admit Short Proofs?