Name
Abstract | ||
|---|---|---|
We resolve an open question by [3]: the exponential complexity of deciding whether a k -CNF has a solution is the same as that of deciding whether it has exactly one solution, both when it is promised and when it is not promised that the input formula has a solution. We also show that this has the same exponential complexity as deciding whether a given variable is backbone (i.e. forced to a particular value), given the promise that there is a solution. We show similar results for True Quantified Boolean Formulas in k -CNF, k -Hitting Set (and therefore Vertex Cover), k -Hypergraph Independent Set (and therefore Independent Set), Max-k -SAT, Min-k -SAT, and 0-1 Integer Programming with inequalities and k -wide constraints. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03351-3_8 | CSR |
Keywords | Field | DocType |
particular value,vertex cover,independent set,exponential complexity,open question,hitting set,hypergraph independent set,input formula,true quantified boolean formulas,integer programming,satisfiability | Discrete mathematics,Combinatorics,Hypergraph,Independent set,Integer programming,Vertex cover,Exponential complexity,True quantified Boolean formula,Mathematics | Conference |
Volume | ISSN | Citations |
5675 | 0302-9743 | 3 |
PageRank | References | Authors |
0.40 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Calabro | 1 | 140 | 6.13 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |