In the parameterized complexity theory, there are some hierarchies of complexity classes. Each such class is closed under fpt-reduction. The most important ones are the '''
W hierarchy
and the A hierarchy'''.
Preliminary definitions In general, there are two ways to define a complexity class: machine-theoretically and logically. In machine theory, a class is defined as the set of decision problems solvable by a class of machines. In logic, a class is defined as the set of decision problems definable by a class of logical formulas.
Boolean circuits The
Hamming weight (
weight for short) of a binary string is the number of ones appearing in it. A Boolean circuit is an acyclic directed graph where the nodes are one of the following gates: AND, OR, NOT. A small gate is a gate with fan-in 0, 1, or 2. Other gates are big. The
weft is the largest number of big gates achievable on any path from an input to the output. The
depth is the largest number of gates (small or big) achievable on any path from an input to the output. By definition, weft ≤ depth. A Boolean circuit is
monotone iff it uses no NOT gate. A Boolean circuit is
antimonotone iff it is of the form \phi(\neg x_1, \dots, \neg x_n) where x_1, \dots, x_n are all its inputs, and \phi is monotone.
Finite model theory Given any: • \mathcal L, a
first-order logical language with a finite set of relation symbols, • \Gamma, a set of
first-order logical formulas in that language, we define \operatorname{p-MC}(\Gamma) to be the
parameterized model checking problem for this tuple. Each problem instance is: • Input: \phi \in \Gamma, and a finite model A for the language \mathcal L • Parameter: |\phi| • Output: Whether A \models \phi A \Sigma_t formula is of the form \exists x_{1,1:m_1}\forall x_{2,1:m_2}\dots Q x_{t,1:m_t} \psi(x), such that the
quantifiers are
alternating between existence and for-all, and the formula inside \psi(x) is quantifier-free (that is, written with just variables, Boolean connectives, and relations). A \Sigma_{t, s} formula is of the form \exists x_{1,1:m_1}\forall x_{2,1:m_2}\dots Q x_{t,1:m_t} \psi(x), with the extra condition that m_2 \leq s, m_3 \leq s, \dots, m_t \leq s.
Definition Machine-theoretically, a parameterized problem is in the class
W[w][d], if there is a fpt-reduction of the problem as follows: • There exists constant integers w, d , such that • every instance (x, k) is transformed in fpt-time to a Boolean circuit that has weft at most
w, and depth at most
d, • (x, k)\in L if and only if the circuit has a satisfying assignment of weight
k. Here we see that "W" stands for "weight". Note that in the above definition, w, d are independent of (x, k) , but the circuit itself depends on (x, k) , and may change if one changes either x or k . The class
W[w] is then defined as their union:W[w][1] \subset W[w][2]\subset \dots \subset W[w] := \bigcup_{d \geq 1} W[w][d]More succinctly,
W[w] is the set of problems fpt-reducible to a family of instance-specific Boolean circuits with weft \leq w and depth bounded by some problem-specific constant. A
normalized circuit of weft
w and depth
d is a circuit, where the first d-w layers contain only small gates, and the last w layers contain alternating big gates of AND and OR. One can iterate the
associative laws and
de Morgan distribution laws to normalize the circuit in fpt-time. Therefore, without loss of generality, we can consider only normalized circuits. Model-theoretically, the class
W[t] is defined as the class of problems fpt-reducible to \operatorname{p-MC}(\Sigma_{t, 1}). While the
W hierarchy is a hierarchy contained in NP, the
A hierarchy more closely mimics the
polynomial-time hierarchy from classical complexity. Machine-theoretically, the A hierarchy of problems are defined as problems that are fpt-reducible to computations by certain kinds of
alternating Turing machines. The "A" stands for "alternating". Examples of
W[1]-complete problems include: Note on the nondeterministic Turing machine. The machine may be specified by one of any of the standard formulations. One usually considers the one-tape Turing machine, but the short Turing machine problem remains
W[1] even if we allow with
f(
k) tapes and even
f(
k) of
f(
k)-dimensional tapes, but even with this extension, the restriction to
f(
k) tape alphabet size is FPT. Crucially, because the machine
M itself is part of the problem input, the input size
n is bigger than the number of states of
M. In this way, the Turing machine can take one of n possible computation paths per step, accessing n^{O(k)} steps in total within time
k. Thus, we see that
W[1] is not obviously contained within
FPT. The independent set problem can be encoded thus. Given each graph (V, E), its independent set problem is encoded by the following weft-1 Boolean circuit:\Phi_{\text{IS}}(V, E) := \bigwedge_{\{u, v\}\in E} (\neg x_u \or \neg x_v)where E is the set of edges in the graph. The graph has an independent set of size
k iff there is a weight-
k input to its Boolean circuit, such that it outputs 1. The clique problem can be coded as \Phi_{\text{clique}}(V, E) := \bigwedge_{\{u, v\} \subset V, u \neq v, \{u, v\}\not\in E} (\neg x_u \or \neg x_v)It checks that any pair vertices that don't make an edge cannot be chosen, so any chosen set of vertices is forced to be a clique. The short Turing machine problem can be converted to a Boolean formula using the same proof idea as of the
Cook–Levin theorem, which shows SAT is NP-complete by coding Turing machine computational traces as Boolean formulas. The following proof is from . Specifically, define the propositional variables: • s_{t, i, j, a, b}: at time
t, the Turing machine is in state
i, and transitions to state
j, reading
a, and writing
b, • y_{t, p, a, b}: at time
t, the tape position
p has symbol
a, and at time
(t+1) has symbol
b. Of the indices, time
t and tape position
p range over
1:k, The ranges of the indices to the Turing machine state
i, j, transition
m, and symbols
a, b are determined by the description of the machine M, but they are both bounded within
1:n. Then, the formula \Phi_{\text{STM}, k}(M, x) is a conjunction of clauses enforcing the following constraints: • Every Turing machine state transition is not disallowed by the nondeterministic transition rule. These look like s_{t, i, j, a, b} \to \neg s_{t+1, i', j', a', b'}, in other words, \neg s_{t, i, j, a, b} \or \neg s_{t+1, i', j', a', b'}. There are O(kn^4) such clauses. • The Turing machine cannot be at two positions at a time, and cannot make two transitions at a time. • Every tape cell state transition is not disallowed by the nondeterministic transition rule. • Every tape cell state cannot have two symbols at a time. • At time 0, the Turing machine is not out of its initial state and position, and
x is not unwritten on the tape. • The Turing machine is not in an unaccepting state at time
k. A computational trace through the Turing machine is then fully specified by setting
k variables of s_{t, i, j, a, b} to True to indicate the Turing machine state transitions at each time, and setting k^2 variables of y_{t, p, a, b} to True to indicate the tape state transition at each time. This reduces the short Turing machine problem to a problem of finding a weight-(k+k^2) satisfying assignment to a weft-1, depth-2, antimonotone Boolean circuit.
W[2] W[2] problems are intuitively of the form: Guess an object of size
k, perform some local processing on the object, then perform one global processing. Examples of
W[2]-complete problems include • deciding if a given graph contains a
dominating set of size
k. • deciding if a given nondeterministic
multi-tape Turing machine accepts within
k steps ("short multi-tape Turing machine acceptance" problem). Crucially, the branching is allowed to depend on
n (like the W[1] variant), as is the number of tapes. An alternate
W[2]-complete formulation allows only single-tape Turing machines, but the alphabet size may depend on
n. The dominating set problem has formula \Psi_{\text{dom}}(V, E) = \bigwedge_{u \in V} \bigvee_{v \in \operatorname{Neighbor}[u]} x_v.
W[i] Some problems are known to be
W[i]-complete, though they are in a computationally generic form, and are usually studied within parameterized complexity theory itself. Empirically, as of 2013, almost all naturally-occurring parameterized problems that they have studied, turned out to be
W[0]-complete,
W[1]-complete, or
W[2]-complete. The following are usually used:
W[SAT] W[SAT] is the class of problems fpt-reducible to weighted SAT problems: • Input: a Boolean formula • Parameter:
k • Output: Whether the formula has a weight-
k satisfying assignment. It contains all
W[t].
W[P] W[P] is the class of problems fpt-reducible to the problem of weighted Boolean circuit problems: It is known that FPT is contained in W[P], and the inclusion is believed to be strict. However, resolving this issue would imply a solution to the
P versus NP problem. Other connections to unparameterised computational complexity are that FPT equals
W[
P] if and only if
circuit satisfiability can be decided in time \exp(o(n))m^{O(1)}, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using nondeterministic choices are in
P.
W[
P] can be loosely thought of as the class of problems where we have a set of items, and we want to find a subset T \subset S of size such that a certain property holds. We can encode a choice as a list of integers, stored in binary. Since the highest any of these numbers can be is , \lceil\log_2 n\rceil bits are needed for each number. Therefore k \cdot \lceil\log_2 n\rceil total bits are needed to encode a choice. Therefore we can select a subset T\subset S with O(k\cdot \log n) nondeterministic choices.
Other classes The
W* hierarchy is similar to the
W hierarchy, but it parameterizes depth, rather than holding it constant. The
W*[t] class is defined as the class of problems fpt-reducible to this problem: • Input: a Boolean circuit of weft at most
t, and depth at most
k, • Parameter:
k • Output: Whether the Boolean circuit has a weight-
k satisfying assignment. It is related to
W by:W^*[1] = W[1], \; W^*[2] = W[2], \; W[t] \subset W^*[t] \subset W[t+2], \quad \forall t \geq 1The
AW hierarchy is obtained by adding alternation to the
W hierarchy. The
AW[t] class is defined as the class of problems fpt-reducible to this problem: • Input: a Boolean circuit of weft at most
t, and a partition of its inputs to I_1 \cup I_2 \cup \cdots \cup I_r • Parameter: (r, k_1, \dots, k_r) • Output: Whether the Boolean circuit is satisfiable under alternating weight-(k_1, \dots, k_r) conditions. The alternating weight-(k_1, \dots, k_r) is defined as follows: • There exists a subset J_1 \subset I_1 of size k_1, such that if we set exactly those inputs to True and the others to False, then, • for any subset J_2 \subset I_2 of size k_2, such that if we set exactly those inputs to True and the others to False, then, • ... • the Boolean circuit outputs True. One can interpret this as a 2-player game, with the first player trying to make the circuit output True, and the second player trying to make the circuit output False. The first player makes a move by setting exactly k_1 inputs of I_1 to True and the others to False, then the second player makes a move on I_2, etc. The circuit is under alternating weight-(k_1, \dots, k_r) conditions iff player 1 has a winning strategy. It turns out that the hierarchy collapses: AW[1] = AW[2] = \cdots. Thus, the literature writes just a common symbol for them: AW[\ast] := AW[1] = AW[2]=\cdots. == See also ==