- Title
- A purely democratic characterization of W[1]
- Creator
- Fellows, Michael; Hermelin, Danny; Muller, Moritz; Rosamond, Frances
- Relation
- Parameterized and Exact Computation: Third International Workshop (IWPEC 2008). Parameterized and Exact Computation (Victoria, BC 14-16 May, 2008) p. 103-114
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-79723-4_11
- Publisher
- Springer Berlin
- Resource Type
- conference paper
- Date
- 2008
- Description
- We give a novel characterization of W[1], the most important fixed-parameter intractability class in the W-hierarchy, using Boolean circuits that consist solely of majority gates. Such gates have a Boolean value of 1 if and only if more than half of their inputs have value 1. Using majority circuits, we define an analog of the W-hierarchy which we call the W-hierarchy, and show that W[1] = W[1] and W[t] ⊆ W[t] for all [t]. This gives the first characterization of W[1] based on the weighted satisfiability problem for monotone Boolean circuits rather than antimonotone. Our results are part of a wider program aimed at exploring the robustness of the notion of weft, showing that it remains a key parameter governing the combinatorial nondeterministic computing strength of circuits, no matter what type of gates these circuits have.
- Subject
- equivalence classes; algorithms; boolean functions; computation theory; parameterization; problem solving
- Identifier
- uon:5972
- Identifier
- http://hdl.handle.net/1959.13/45028
- Identifier
- ISBN:9783540797227
- Reviewed
- Hits: 3508
- Visitors: 3465
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|