Probabilistic Analysis of Algorithms for NP-Complete Problems

Abstract

This is the final scientific report describing results obtained under Air Force Office of Scientific Research grant number AFOSR-84-0372. The main objective was the probabilistic sense, it is easy to find a satisfying truth assignment to an instance of satisfiability but it is hard to verify that an unsatisfiable instance has a solution. A side issue was the analysis of probabilistic models used to obtain the main results.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 29, 1989
Accession Number
ADA217880

Entities

People

  • John Franco

Organizations

  • Indiana University Bloomington

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Applied Mathematics
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Hash Tables
  • Information Science
  • Models
  • Natural Languages
  • New Jersey
  • Operations Research
  • Probabilistic Models
  • Probability
  • Programming Languages
  • Scientific Research
  • United States

Readers

  • Operations Research
  • Technical Research and Report Writing.