1
$\begingroup$

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?

$\endgroup$
3
  • $\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$ Commented Mar 28, 2015 at 18:26
  • $\begingroup$ @Juho The complement of a decision problem is a completely standard concept. $\endgroup$ Commented Mar 28, 2015 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
    Commented Mar 28, 2015 at 20:20

1 Answer 1

2
$\begingroup$

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

$\endgroup$
9
  • $\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$ Commented Mar 31, 2015 at 18:42
  • $\begingroup$ I can't follow your reasoning. Try to write it again more clearly. $\endgroup$ Commented Mar 31, 2015 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$ Commented Mar 31, 2015 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$ Commented Mar 31, 2015 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$ Commented Mar 31, 2015 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.