Generating Hard Satisfiability Problems Export

@article{citeulike:6032644, abstract = {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.}, author = {Mitchell, David and Selman, Bart and Levesque, Hector J.}, citeulike-article-id = {6032644}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0004-3702(95)00045-3}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/0004-3702(95)00045-3}, doi = {10.1016/0004-3702(95)00045-3}, issn = {00043702}, journal = {Artificial Intelligence}, keywords = {empirical\_hardness, satisfiability, seminal}, month = {March}, number = {1-2}, pages = {17--29}, posted-at = {2009-10-29 17:32:05}, priority = {2}, title = {{Generating Hard Satisfiability Problems}}, url = {http://dx.doi.org/10.1016/0004-3702(95)00045-3}, volume = {81}, year = {1996} }

TY - JOUR ID - citeulike:6032644 L3 - citeulike-article-id:6032644 N2 - 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. IS - 1-2 JF - Artificial Intelligence SN - 00043702 EP - 29 TI - {Generating Hard Satisfiability Problems} VL - 81 SP - 17 KW - empirical_hardness KW - satisfiability KW - seminal AU - Mitchell, David AU - Selman, Bart AU - Levesque, Hector PY - 1996/03// UR - http://dx.doi.org/10.1016/0004-3702(95)00045-3 ER -