By definition, a parameterized problem $(Q, \kappa)$ is in $W[1]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.

On the other hand, $(Q, \kappa) \in A[1]$, if it can be transformed into a parameterized model checking problem $p$ -$MC(\Sigma_1)$.

Finally, $(Q, \kappa) \in W[1] \Leftrightarrow (Q, \kappa) \in A[1]$ holds. However, I did not see why a parameterized model checking problem has to have weft 1. It occurs to me as if $W[1] \subseteq A[1]$.

Why are they the same class?


The proofs can be found in the literature. I'll try to explain the intuition.

The short version is that parameterized independend set is typical for both $W[1]$ and $A[1]$.

The general intuition about the $W$- and the $A$-hierarchy is that they are about amounts of nondeterminism. In particular, at the first levels, both hierarchies allow existential nondeterminism with $n^k$ possibilities to choose from, followed by universal nondeterminism with $n$ possibilities, followed by existential nondeterminism with a constant number of possibilities. Let us see that for each of the three problems.

  1. Independend set is the question:

    • Is there a set of $k$ vertices,
    • such that for all edges
    • there is an endpoint not in the set?

    The first bullet point is existential ("is there?") with $\binom nk$ possibilities. Up to parameterized reductions there is no difference between $\binom nk$ and $n^k$. The second point is universal ("for all") with as many possibilities as there are edges. Which is bounded by the input size $n$. The last part is existential ("there is") with $2$ possibilities ($2$ endpoints per edge).

  2. In the case of $W[1]$, that is of parameterized weighted $c$-CNF-SAT, the first existential nondeterminism concern the set of variables to set to true, much like the vertex set above. The universal nondeterminism ranges over the clauses, all of which have to be satisfied. Their number is bounded by $n$. The last part is existential, namely finding an atom in the clause that is satisfied. That part has at most $c$ possibilities.

  3. For model checking of $\Sigma_1$, it is not obvious at first that the above nondeterminism suffices. We will have to do some normalization of $\Sigma_1$ formulae. First, let us assume that the quantifier-free part is in DNF. Achieving DNF may bring an exponential blow-up, but as the formula is the parameter, any blow-up is fine. Second, let there be a bound $r$ on the arity of relations (I will not go into the details of how to do that). Last, let all atoms be negative (that can be achieved by adding complements for all relations with an $n^r$ blowup.

    Now the quantifiers incur existential nondeterminism with $n$ possibilites each, for a total of $n^k$. The disjunctive part of the DNF brings another existential $n$. The resulting $n^{k+1}$ is as well as $n^k$ under parameterized reductions. Then comes a conjunctive clause for universal nontederminism with $k$ possibilities. Then comes a negated relational atom: For all tuples in the relation ($n$ (universal) possibilities, because the relation is part of the input) there is some position ($r$ existential possibilities) at which the tuple differs from the values chosen for the quantifiers. Again, think of independent set, where $r=2$. The universal part totals to $k\cdot n$, which is as well as $n$ under reductions.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.