A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems

Abstract

In this paper we develop a general-purpose algorithm that can solve a number of NP-complete problems in time $T = O(2^{n/2} )$ and space $S = O(2^{n/4} )$. The algorithm can be generalized to a family of algorithms whose time and space complexities are related by $T \cdot S^2 = O(2^n )$. The problems it can handle are characterized by a few decomposition axioms; they include knapsack problems, exact satisfiability problems, set covering problems, etc. The new algorithm has considerable cryptanalytic significance, since it can break knapsack-based cryptosystems with up to $n = 100$ generators.