The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

by Bo Moon

Submitted : Fall 2012

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

[ Back ]