Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top