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
scroll top