2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Please make "2" more precise. That was rather loose there. Which type of reduction are you talking about? Karp reduction, or Cook reduction? $\endgroup$
    – D.W. ♦
    Sep 24, 2018 at 0:02
  • $\begingroup$ 2 is a Cook reduction. $\endgroup$
    – RTK
    Sep 24, 2018 at 0:05
  • 1
    $\begingroup$ Note that at the very least you have to assume $P\not = NP$ because otherwise taking $A$ to be the empty language would falsify your statement. $\endgroup$
    – Tom van der Zanden
    Sep 24, 2018 at 7:58
  • $\begingroup$ I think if $P=NP$ and $A$ is the empty language then (2) will still hold since the chosen coNP-complete problem $P$ will be still solvable in poly-time; but with no call of the algorithm solving $A$. Am I missing something? $\endgroup$
    – RTK
    Sep 24, 2018 at 8:19
  • $\begingroup$ Your logic would show $A$ to be $coNP$-complete even though it isn't. $\endgroup$
    – Tom van der Zanden
    Sep 24, 2018 at 10:11

1 Answer 1

Reset to default
2
$\begingroup$

No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness.

SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions.

Some questions on this site which are relevant are this one and that one, as well as a few others.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! Can I with (1) and (2) conclude that $A$ is Cook-coNP-complete? considering the Cook-coNP completeness defined similarly as the coNP completeness but with the Cook reduction. $\endgroup$
    – RTK
    Sep 25, 2018 at 16:50
  • 1
    $\begingroup$ If you define a Cook-coNP-complete problem to be one that satisfies (1) and (2), then any problem that satisfies (1) and (2) is Cook-coNP-complete, by definition. $\endgroup$
    – Yuval Filmus
    Sep 25, 2018 at 17:13
  • $\begingroup$ Please according to my second preoccupation when using only CooK reduction does it matter if the chosen problem to be reduced is p-complete or coNP complete? In other words when showing that a problem $A$ is Cook NP-hard* could I Cook reduce a coNP-complete (such as TAUT, UNSAT) problem to $A$ instead of an NP-complete (SAT) to A? $\endgroup$
    – RTK
    Sep 25, 2018 at 18:00
  • 1
    $\begingroup$ A problem is Cook-NP-hard iff it is Cook-coNP-hard. $\endgroup$
    – Yuval Filmus
    Sep 25, 2018 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.