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?

  • $\begingroup$ 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 $\endgroup$ – Teodorico Levoff Mar 28 '15 at 18:26
  • $\begingroup$ @Juho The complement of a decision problem is a completely standard concept. $\endgroup$ – David Richerby Mar 28 '15 at 20:09
  • $\begingroup$ @DavidRicherby Sure. Given the string of questions from the same user, I was only making sure everyone was on the same page. $\endgroup$ – Juho Mar 28 '15 at 20:20

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?).

  • $\begingroup$ 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? $\endgroup$ – Teodorico Levoff Mar 31 '15 at 18:42
  • $\begingroup$ I can't follow your reasoning. Try to write it again more clearly. $\endgroup$ – Yuval Filmus Mar 31 '15 at 18:45
  • $\begingroup$ 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. $\endgroup$ – Teodorico Levoff Mar 31 '15 at 18:49
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 31 '15 at 18:51
  • 2
    $\begingroup$ 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." $\endgroup$ – Yuval Filmus Mar 31 '15 at 19:06

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.