A hierarchy of tractable subclasses for SAT and counting SAT problems

A hierarchy of tractable subclasses for SAT and counting SAT problems

Finding subclasses of formulae for which the SAT problem can be solved in polynomial time has been an important problem in computer science. We present a new hierarchy of propositional formulae subclasses for which the SAT and counting SAT problems can be solved in polynomial time. Our tractable sub...

Full description

Bibliographic Details
Main Authors: Rinard, Martin C., Grigoras, Gheorghe, Andrei, Stefan, Yap, Roland Hock Chuan
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Institute of Electrical and Electronics Engineers 2010
Subjects:
SAT and Counting SAT Problems
Tractable Subclasses
Online Access:http://hdl.handle.net/1721.1/58881
https://orcid.org/0000-0001-8095-8523

Internet

http://hdl.handle.net/1721.1/58881
https://orcid.org/0000-0001-8095-8523

Similar Items