Parameterized complexity: Difference between revisions

Revision as of 13:17, 25 August 2023

Revision as of 23:42, 16 November 2023

Line 34:

=== ''W'' hierarchy ===

The '''''W'' hierarchy''' is a collection of computational complexity classes. A parameterized problem is in the class ''W''[''i''], if every instance <math>(x, k)</math> can be transformed (in fpt-time) to a combinatorial circuit that has [[weft (circuit)|weft]] at most ''i'', such that <math>(x, k)\in L</math> if and only if there is a satisfying assignment to the inputs that assigns ''1'' to exactly ''k'' inputs. The '''weft''' is the largest number of logical units with fan-in greater than two on any path from an input to the output. The total number of logical units on the paths (known as depth) must be limited by a constant that holds for all instances of the problem.

Note that <math>\mathsf{FPT} = W[0]</math> and <math>W[i] \subseteq W[j]</math> for all <math>i\le j</math>. The classes in the ''W'' hierarchy are also closed under fpt-reduction.

A complete problem for ''W''[''i''] is '''Weighted ''i''-Normalized Satisfiability''':<ref>{{cite journal |last1=Downey |first1=Rod G. |last2=Fellows |first2=Michael R. |title=Fixed-Parameter Tractability and Completeness I: Basic Results |journal=SIAM Journal on Computing |date=August 1995 |volume=24 |issue=4 |pages=873–921 |doi=10.1137/S0097539792228228 |url=https://doi.org/10.1137/S0097539792228228 |language=en |issn=0097-5397}}</ref> given a Boolean formula written as an AND of ORs of ANDs of ... of possibly negated variables, with <math>i+1</math> layers of ANDs or ORs (and ''i'' alternations between AND and OR), can it be satisfied by setting exactly ''k'' variables to 1?

Many natural computational problems occupy the lower levels, ''W''[1] and ''W''[2].