Est-ce une façon correcte de montrer qu'un problème est CONP-Complete?
-
05-11-2019 - |
Question
Laisser $ A $ être un problème que je veux montrer que c'est conp-complet. Je sais que je pourrais juste montrer son complément $ bar {a} $ est NP-complete ou que $ bar {a} $ est en NP et pour un problème de conp-complete $ Q $, montre CA $ Q $ peut être Karp-réduit à $ A $.
Mais je me demande si les étapes suivantes sont suffisantes pour montrer que UN est conp-complet?
- Montre CA $ A $ est dans $ conp $ en montrant que son complément est en np
- Choisissez-en un conp-complet problème $ Q $ et Cuire à cuire à $ A $.
La classe CONP-Complete est-elle toujours distinguable (sous l'hypothèse $ P neq np $) de la classe NP-complete? Puisqu'il semble que tout problème CONP-Complete est Turing-Polynomialement équivalent à tout autre problème NP-Complete.
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange