The Emerging Theory of Average-Case Complexity

Abstract

A primary contribution of theoretical computer science has been the identification of the so-called NP-complete problems, a well-known class of problems provably equivalent to one another in worst-case computational complexity, modulo polynomial-time computation. These problems, being the hardest in the class NP, are widely believed to be unsolvable by any polynomial- time algorithm, and indeed, no sub-exponential time algorithm is known for any NP-complete problem. This paper reviews some of the recent results that have emerged in the study of average-case complexity. Included is a description of Levin's framework for studying average-case complexity, as well as his proof of the existence of complete problems for a class of distributional problems. The paper also presents some new results, including a natural and more liberal extension of Levin's model, in addition to a partial characterization of the relationships among the new average-case complexity classes. (kr)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1990
Accession Number
ADA222821

Entities

People

  • Robert E. Schapire

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Classification
  • Computational Complexity
  • Computations
  • Computer Science
  • Distribution Functions
  • Language
  • Machines
  • Notation
  • Numbers
  • Polynomials
  • Probability
  • Random Variables
  • Security
  • Standards
  • Theoretical Computer Science

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.
  • Operations Research
  • Theoretical Analysis.