In this paper we develop a general-purpose algorithm that can solve a number of NP-complete problems in time T = O(2n/2 ) and space S = O(2n/4 ). The algorithm can be generalized to a family of algorithms whose time and space complexities are related by T · S² = O(2ⁿ ). 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.
No takes yet. Share an insight, caveat, or question.
Schroeppel et al. (1981) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: