# Is this a correct way to show that a problem is coNP-complete?

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.

• Please make "2" more precise. That was rather loose there. Which type of reduction are you talking about? Karp reduction, or Cook reduction?
– D.W.
Sep 24, 2018 at 0:02
• 2 is a Cook reduction.
– RTK
Sep 24, 2018 at 0:05
• 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. Sep 24, 2018 at 7:58
• 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?
– RTK
Sep 24, 2018 at 8:19
• Your logic would show $A$ to be $coNP$-complete even though it isn't. Sep 24, 2018 at 10:11

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.

• 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.
– RTK
Sep 25, 2018 at 16:50
• 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. Sep 25, 2018 at 17:13
• 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?
– RTK
Sep 25, 2018 at 18:00
• A problem is Cook-NP-hard iff it is Cook-coNP-hard. Sep 25, 2018 at 18:00