سؤال

Let $A$ be a problem that I want to show it is coNP-complete. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show that $Q$ can be Karp-reduced to $A$.

But I wonder if the following steps are sufficient to show that A is coNP-complete?

  1. Show that $A$ is in $coNP$ by showing that its complement is in NP
  2. Choose one coNP-complete problem $Q$ and Cook-reduce it to $A$.

Does the coNP-complete class still be distinguishable (under the assumption $P\neq NP$) from the NP-complete class? since it seems that any coNP-complete problem is Turing-polynomially equivalent to any other NP-Complete problem.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top