There are no CNF problems

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

4 Citations (Scopus)

Abstract

SAT technology has improved rapidly in recent years, to the point now where it can solve CNF problems of immense size. But solving CNF problems ignores one important fact: there are NO problems that are originally CNF. All the CNF that SAT solvers tackle is the result of modelling some real world problem, and mapping the high-level constraints and decisions modelling the problem into clauses on binary variables. But by throwing away the high level view of the problem SAT solving may have lost a lot of important insight into how the problem is best solved. In this talk I will hope to persuade you that by keeping the original high level model of the problem one can realise immense benefits in solving hard real world problems.

Original languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing, SAT 2013 - 16th International Conference, Proceedings
PublisherSpringer
Pages19-21
Number of pages3
ISBN (Print)9783642390708
DOIs
Publication statusPublished - 15 Jul 2013
Externally publishedYes
Event16th International Conference on Theory and Applications of Satisfiability Testing, SAT 2013 - Helsinki, Finland
Duration: 8 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7962 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Theory and Applications of Satisfiability Testing, SAT 2013
CountryFinland
CityHelsinki
Period8/07/1312/07/13

Cite this

Stuckey, P. J. (2013). There are no CNF problems. In Theory and Applications of Satisfiability Testing, SAT 2013 - 16th International Conference, Proceedings (pp. 19-21). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7962 LNCS). Springer. https://doi.org/10.1007/978-3-642-39071-5_3