# 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 '18 at 0:02
• 2 is a Cook reduction. – RTK Sep 24 '18 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. – Tom van der Zanden Sep 24 '18 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 '18 at 8:19
• Your logic would show $A$ to be $coNP$-complete even though it isn't. – Tom van der Zanden Sep 24 '18 at 10:11

• 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 '18 at 16:50
• 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 '18 at 18:00