Accession Number:

ADA080385

Title:

A T = 0(2n/2), S = 0(2/4) Algorithm for Certain NP-Complete Problems,

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-01-01

Pagination or Media Count:

26.0

Abstract:

In this paper we develop a general purpose algorithm that can solve a number of NP-complete problems in time T02 to the m2 power and space S02 to the m4 power. The algorithm can be generalized to a family of algorithms whose time and space complexities are related by TS202 to the ninth power. The problems it can handle are characterized by a few decomposition axioms, and they include knapsack problems, exact satisfiability problems, set covering problems, etc. The new algorithm has a considerable cryptanalytic significance, since it can break knapsack-based cryptosystems with up to n 100 generators. Author

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE