Name
Abstract | ||
|---|---|---|
Abstract We consider the relationship between the complexities of -,and those of,restricted to formulas of constant density. Let be the infimum of those,such that - on variables can be decided in time,and,be the infimum of those,such that on variables and clauses can be decided in time,. We show that,. So, for any , - can be solved in time independent of,if and only if the same is true for,with any fixed density of clauses to variables. We derive some interesting consequencesfrom this. For example, assumingthat - is exponentially hard (that is, ), of any fixed density can be solved in time whose exponent is strictly less than that for general,. We also give an improvement to the sparsificationlemma of [12] showing that instances of -,of density slightly more than exponential in,are almost the hardest instances of,-,. The previous result showed,this for densities doubly exponential in . |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/CCC.2006.6 | IEEE Conference on Computational Complexity |
Keywords | DocType | ISSN |
clause width,clause density,computational complexity,computability | Conference | 1093-0159 |
ISBN | Citations | PageRank |
0-7695-2596-2 | 55 | 1.94 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Calabro | 1 | 140 | 6.13 |
| Russell Impagliazzo | 2 | 5444 | 482.13 |
| Ramamohan Paturi | 3 | 1260 | 92.20 |