Thumbnail
Access Restriction
Open

Author Mitchell, David ♦ Selman, Bart ♦ Levesque, Hector
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Sat Problem ♦ Easy Distribution ♦ Right Distribution ♦ Input Size ♦ Satisfiability Testing ♦ Np-hard Task Degrades ♦ Appropriate Parameter Value ♦ Acceptable Behavior ♦ Introduction Many Computational Task ♦ Large-scale Experiment ♦ Satisfiability-testing Procedure ♦ Small Increase ♦ Random Formula ♦ General Form ♦ Ai Community ♦ Fundamental Disagreement
Description We report results from large-scale experiments in satisfiability testing. As has been observed by others, testing the satisfiability of random formulas often appears surprisingly easy. Here we show that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult. Our results provide a benchmark for the evaluation of satisfiability-testing procedures. Introduction Many computational tasks of interest to AI, to the extent that they can be precisely characterized at all, can be shown to be NP-hard in their most general form. However, there is fundamental disagreement, at least within the AI community, about the implications of this. It is claimed on the one hand that since the performance of algorithms designed to solve NP-hard tasks degrades rapidly with small increases in input size, something will need to be given up to obtain acceptable behavior....
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1992-01-01