Name
Abstract | ||
|---|---|---|
We give a novel characterization of W[1], the most importantfixed-parameter intractability class in the W-hierarchy, using Booleancircuits that consist solely of majority gates. Such gates have a Booleanvalue of 1 if and only if more than half of their inputs have value 1. Usingmajority circuits, we define an analog of the W-hierarchy which wecall the W-hierarchy, and show that W[1] = W[1] and W[t] ⊆ W[t] forall t. This gives the first characterization of W[1] based on the weightedsatisfiability problem for monotone Boolean circuits rather than antimonotone.Our results are part of a wider program aimed at exploringthe robustness of the notion of weft, showing that it remains a key parametergoverning the combinatorial nondeterministic computing strength ofcircuits, no matter what type of gates these circuits have. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-79723-4_11 | IWPEC |
Keywords | Field | DocType |
boolean circuits,satisfiability | Discrete mathematics,Boolean circuit,Nondeterministic algorithm,Theoretical computer science,Robustness (computer science),If and only if,Electronic circuit,Monotone polygon,Computable function,Mathematics | Conference |
Volume | ISSN | ISBN |
5018 | 0302-9743 | 3-540-79722-X |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Danny Hermelin | 2 | 790 | 48.62 |
| Moritz Müller | 3 | 48 | 9.08 |
| Frances A. Rosamond | 4 | 304 | 15.94 |