Abstract | ||
---|---|---|
We show analogues of a theorem due to Valiant and Vazirani (16) for intractable parameterized complexity classes such as W(P), W(SAT) and the classes of the W-hierarchy as well as those of the A-hierarchy. We do so by proving a general "logical" version of it which may be of independent interest. |
Year | Venue | Field |
---|---|---|
2008 | Electronic Colloquium on Computational Complexity (ECCC) | Discrete mathematics,Combinatorics,Parameterized complexity,Lemma (mathematics),Mathematics |
DocType | Volume | Issue |
Journal | 15 | 063 |
Citations | PageRank | References |
7 | 0.40 | 9 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Moritz Müller | 1 | 7 | 0.73 |