Pourquoi $ w [1] = a [1] $ Hold?
-
05-11-2019 - |
Question
Par définition, un problème paramétré $ (q, kappa) $ est dans $ w [1] $ s'il peut être transformé en un circuit combinatoire $ varphi $ en temps polynomial, de sorte que la trame de $ varphi $ est 1 .
D'un autre côté, $ (q, kappa) dans un [1] $, s'il peut être transformé en un problème de vérification de modèle paramétré $ p $ - $ mc ( Sigma_1) $.
Enfin, $ (q, kappa) in w [1] leftrightarrow (q, kappa) dans un [1] $ détient. Cependant, je n'ai pas vu pourquoi un problème de vérification de modèle paramétré doit avoir la trame 1. Il me semble que si $ w [1] subseseq a [1] $.
Pourquoi sont-ils la même classe?
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange