# What can I deduce if an NP-complete problem is reducible to its complement?

Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I could possibly make about this kind of relationship?

• Given a decision problem X, its complement X Complement is the collection of all instances s such that s is not in X. Slide 5 on this, courses.engr.illinois.edu/cs473/fa2010/Lectures/lecture24.pdf – Teodorico Levoff Mar 28 '15 at 18:26
• @Juho The complement of a decision problem is a completely standard concept. – David Richerby Mar 28 '15 at 20:09
• @DavidRicherby Sure. Given the string of questions from the same user, I was only making sure everyone was on the same page. – Juho Mar 28 '15 at 20:20

## 1 Answer

If an NP-complete problem is reducible to its complement then NP=coNP (why?). Conversely, if NP=coNP then every NP-complete problem is reducible to its complement (why?).

• I will give my attempt, correct me for any mistakes. Suppose A is NP-complete, if NP=coNP, then A is in NP = coNP. If A is in P, then let A's complement be in NP> and It's complement is polytime reducible to A(So A is NP-hard), --> A's complement is in coNP, So NP = coNP? – Teodorico Levoff Mar 31 '15 at 18:42
• I can't follow your reasoning. Try to write it again more clearly. – Yuval Filmus Mar 31 '15 at 18:45
• Suppose A is NP-complete. A is in coNP by definition of coNP, because A complement is in NP. If NP=coNP, then A is polytime reducible to A's complement, and vice versa. If A is reducible to its complement then we can map through a function computable in polytime, from NP to coNP? My apologies, it's kind of messy and hard to follow. – Teodorico Levoff Mar 31 '15 at 18:49
• I'm sorry, but I still can't follow. What are you assuming, and what are you trying to prove? Also, it is (probably) not true that if A is NP-complete then it is in coNP; if an NP-complete problem is in coNP then NP=coNP. – Yuval Filmus Mar 31 '15 at 18:51
• Try filling the following template. "We start by showing that if an NP-complete problem is reducible to its complement then NP=coNP. Suppose that A is an NP-complete reducible to its complement, and let B$\in$NP. Then ... and so B$\in$coNP. This shows that NP$\subseteq$coNP, and so NP=coNP. Next, we show that if NP=coNP then every NP-complete problem is reducible to its complement. Suppose that NP=coNP, and let A be an NP-complete problem. Then ... and so A is reducible to its complement." – Yuval Filmus Mar 31 '15 at 19:06