A T = 0(2n/2), S = 0(2/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=0(2 to the m/2 power) and space S=0(2 to the m/4 power). The algorithm can be generalized to a family of algorithms whose time and space complexities are related by TS2=0(2 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA080385

Entities

People

  • Adi Shamir
  • Richard Schroeppel

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Additives (Chemicals)
  • Algorithms
  • Computer Programming
  • Computer Science
  • Computers
  • Cryptography
  • Decomposition
  • Generators
  • Information Systems
  • Information Theory
  • Linear Algebra
  • Mathematical Analysis
  • Military Research
  • New York
  • Polynomials
  • Technical Information Centers
  • Theorems

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Electrical Engineering
  • Mathematical Modeling and Probability Theory.
  • Operations Research

Technology Areas

  • Space