# 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

• 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