![](/images/graphics-bg.png)
On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls
Author
Source
Journal of Applied Mathematics and Decision Sciences
Issue
Vol. 2009, Issue 2009 (31 Dec. 2009), pp.1-18, 18 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2009-07-20
Country of Publication
Egypt
No. of Pages
18
Main Subjects
Abstract EN
This paper is concerned with the computational complexities of three types of queries, namely, satisfiability, equivalence, and hull inclusion.
The first two queries are analyzed over the domain of CNF formulas, while hull inclusion queries are analyzed over continuous and discrete sets defined by rational polyhedra.
Although CNF formulas can be represented by polyhedra over discrete sets, we analyze them separately on account of their distinct structure.
In particular, we consider the NAESAT and XSAT versions of satisfiability over HornCNF, 2CNF, and Horn⊕2CNF formulas.
These restricted families find applications in a number of practical domains.
From the hull inclusion perspective, we are primarily concerned with the question of checking whether two succinct descriptions of a set of points are equivalent.
In particular, we analyze the complexities of integer hull inclusion over 2SAT and Horn polyhedra.
Hull inclusion problems are important from the perspective of deriving minimal descriptions of point sets.
One of the surprising consequences of our work is the stark difference in complexities between equivalence problems in the clausal and polyhedral domains for the same polyhedral structure.
American Psychological Association (APA)
Subramani, K.. 2009. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences،Vol. 2009, no. 2009, pp.1-18.
https://search.emarefa.net/detail/BIM-502829
Modern Language Association (MLA)
Subramani, K.. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences No. 2009 (2009), pp.1-18.
https://search.emarefa.net/detail/BIM-502829
American Medical Association (AMA)
Subramani, K.. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences. 2009. Vol. 2009, no. 2009, pp.1-18.
https://search.emarefa.net/detail/BIM-502829
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-502829