Probabilistic Analysis of Algorithms for NP-Complete Problems
Abstract
During this period the investigator produced papers with titles, Duality, finite improvement and efficiently solved optimization problems, Sensitivity of probabilistic results on algorithm for NP-complete problems to input distribution, and a third, being written now, Probabilistic analysis of algorithms for the satisfiability problem. The first shows that it is highly unlikely that an NP-complete problem can be solved by any of a certain broad class of algorithms. The second shows that favorable results on a certain set of problems are misleading. That is if another input distribution is used the algorithms perform badly in the probabilistic sense. The main result in the third is that the satisfiability problem, an NP-complete problem, can be solved efficiently in the probabilistic sense under a distribution which causes no misleading results. The report summarizes results of research conducted under the grant during the inclusive dates. (KR)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1983
- Accession Number
- ADA215160
Entities
People
- John Franco
Organizations
- Case Western Reserve University