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?

  1. Montre CA $ A $ est dans $ conp $ en montrant que son complément est en np
  2. 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
scroll top