𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating hard satisfiability problems

✍ Scribed by Bart Selman; David G. Mitchell; Hector J. Levesque

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
975 KB
Volume
81
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

A Dichotomy Theorem for Maximum Generali
A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
✍ N. Creignou πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 930 KB

We study the complexity of an infinite class of optimization satisfiability problems. Each problem is represented through a finite set, \(S\), of logical relations (generalizing the notion of clauses of bounded length). We prove the existence of a dichotomic classification for optimization satisfiab

Generalized satisfiability problems: min
Generalized satisfiability problems: minimal elements and phase transitions
✍ Nadia Creignou; HervΓ© DaudΓ© πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 263 KB

We develop a probabilistic model on the generalized satisΓΏability problems deΓΏned by Schaefer (in: Proceedings of the 10th STOC, San Diego, CA, USA, Association for Computing Machinery, New York, 1978, pp. 216 -226) for which the arity of the constraints is ΓΏxed in order to study the associated phas