On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls (Q1040040): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q58646855, #quickstatements; #temporary_batch_1706974296281 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58646855 / rank | |||
Normal rank |
Revision as of 19:03, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls |
scientific article |
Statements
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls (English)
0 references
23 November 2009
0 references
Summary: 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\(\oplus \)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.
0 references
computational complexity
0 references
satisfiability
0 references
equivalence
0 references
hull inclusion
0 references
polyhedral structure
0 references