Pourquoi la domination est-elle définie dans $ w [2] $, mais indépendant définie $ w [1] $
-
05-11-2019 - |
Question
Dans Complexité paramétrée la Problème d'ensemble indépendant pour un paramètre $ k $ it $ W [1] $-complete, et Ensemble dominant est $ W [2] $-Achevée. Maintenant le prototypique $ W [1] $ Le problème est de décider par une machine de turing non déterministe monomorolique si elle a une course d'acceptation avec au plus $ k $ Stepts, et pour $ W [2] $ C'est la même notion avec une machine multipape.
Intuitivement, ce sont tous deux des problèmes de sélection de réglage, donc une machine non déterministe peut deviner au plus $ k $ étapes quels éléments prendre dans un ensemble indépendant (ou dominant). Donc, avec cette intuition, que le premier problème est $ W [1] $ Est-ce clair, mais pas pourquoi l'ensemble dominant n'est pas? Alors, qu'est-ce que je manque, quelle est la fonction de distinction, pourquoi avons-nous besoin d'une machine multipape pour la seconde, mais pas pour la première? Mon intestin mettrait la domination mise en place dans $ W [1] $, mais ce n'est pas vrai comme je le sais.
ÉDITER: J'ai pris la définition de la machine Turing de $ W [1] $ du papier séminal suivant Tradabilité et exhaustivité des paramètres fixes I: résultats de base, mais il est également écrit sur Wikipédia, avec la caractérisation de $ W [2] $. Si vous n'avez pas accès au papier, vous pouvez obtenir un PDF d'ici, mais les diagrammes sont manquants là-bas (voir page 6 pour la définition du problème de la machine Turing).
Pas de solution correcte