Why does $W[1] = A[1]$ hold?
-
05-11-2019 - |
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