Probabilistic Analysis of Algorithms for NP-Complete Problems.

Abstract

The goal of this research is to develop and analyze algorithms which can, in some practical sense, solve certain NP-complete problems efficiently. By solve we mean determine whether a solution to a given instance of an NP-complete problem exists where, for the problems we have considered, a solution is an assignment of values to a list of variables which cause some predicate to be true. We do not consider actually finding solutions when they exist since doing so adds unnecessary complexity to the statement of the algorithms: the algorithms we consider can all be modified to find solutions without significantly altering performance. NP-complete problems are found in Crytology, Operations Research, Artificial Intelligence, Computer System Design and many other areas. There is no known algorithm for any NP-complete problem which runs in time bounded by a polynomial on the length of the input (polynomial time) in the worst case nor is one likely to be found. We seek algorithms which solve nearly every instance of specific NP-complete problems in polynomial time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1984
Accession Number
ADA148207

Entities

People

  • J. Franco

Organizations

  • Case Western Reserve University

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Classification
  • Computer Science
  • Computers
  • Engineering
  • Operations Research
  • Polynomials
  • Probability
  • Probability Distributions
  • Scientific Research
  • Systems Engineering
  • United States
  • Weighting Functions

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms