-4
$\begingroup$

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more:

Suppose that A is NP-Complete, but B is in P. I claim that A\B is NP-Complete and B\A is NP-Complete as well. To see this, assume first that A\B is in P, and let X and Y be polynomial-time algorithms for B and for A\B, respectively. "Concatenating" X and Y as follows yields an algorithm Z for A:

Given L, test L using X; if X outputs "yes", test using Y; if Y yields "yes", output "no" and stop; if X yields "no", output "no" and stop; output "yes" otherwise and stop.

This algorithm Z runs in polynomial time, because if the (polynomial time) complexity exponent of X is k and the (polynomial time) complexity exponent of Y is n, then this algorithm clearly has (polynomial time) complexity exponent m=max(k,n). This would provide proof that P=NP, so A\B is NP-Complete.

Now suppose that B\A is in P. This time, let Y' be a polynomial-time algorithm for B\A and let X be as above. We construct an algorithm Z' for A, as follows:

Given L, test L using X; if X outputs "yes", test using Y'; if Y yields "no", output "yes" and stop; if X yields "no", test using Y'; if Y yields "no", output "yes" and stop; output "no" otherwise and stop.

This yields a polynomial-time algorithm for A, and so again, this would entail that P=NP, so B\A also is NP-Complete.

+++++++++End of Example++++++++++++

While I don't see anything wrong with the above at the moment, perhaps I have a mistake or complexity miscalculation? ...because for a while, as I was writing the second algorithm, I began to think it was odd and perhaps impossible that I can be right about B\A also being NP-Complete...

As I said, I'm somewhat new to this area, so feedback would be appreciated.

$\endgroup$
1
$\begingroup$

Let $C$ be any language in $NP \setminus \{ \emptyset \}$. Notice that such a $C$ exists (e.g., $C = \Sigma^*$).

The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $A \setminus B$ is $NP$-complete" is false (regardless of whether $P=NP$). To see this pick $B=\Sigma^*$. Then $A \setminus B = \emptyset$. Since there is no polynomial-time reduction from $C$ to $A \setminus B $, we know that $A \setminus B$ cannot be $NP$-hard and hence cannot be $NP$-complete.

Substituting $B=\Sigma^*$ in your argument, you obtain an algorithm $Z$ that accepts $\Sigma^*$, but $\Sigma^* \neq A$ (since $A$ is $NP$-complete). This shows that your claim that $Z$ is an algorithm for $A$ is wrong.

The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $B \setminus A$ is $NP$-complete" is also false (regardless of whether $P=NP$). To see this simply pick $B = \emptyset$. Since there is no polynomial-time reduction from $C$ to $B \setminus A$ we know that $B \setminus A$ cannot be $NP$-hard and hence cannot be $NP$-complete.

Substituting $B=\emptyset$ in your argument, you obtain an algorithm $Z'$ that accepts $\Sigma^*$, hence $Z'$ is not an algorithm for $A \neq \Sigma^*$.

Another logical error that you have in your proof is assuming that the complement of "$A \setminus B$ (resp. $B \setminus A$) is in $P$" is "$A \setminus B$ (resp. $B \setminus A$) is $NP$-complete". If $P \neq NP$ then there are problems in $NP \setminus P$ that are not $NP$-complete. See Ladner's theorem and the class $NP$-Intermediate.

$\endgroup$
6
  • $\begingroup$ Your answer does not address the question. The question was "What is wrong with this argument...", not "Is it true that if 𝐴 is 𝑁𝑃-Complete and 𝐵 is in 𝑃 then 𝐴∖𝐵 is 𝑁𝑃-complete?". $\endgroup$ Jul 24 at 21:32
  • $\begingroup$ The answer provides a counterxample. Once you substitute $B = \Sigma^*$ and $B=\emptyset$ in the proposed proofs it's obvious where they break down. $\endgroup$
    – Steven
    Jul 24 at 21:35
  • $\begingroup$ That's not at all obvious for people who don't already know your notation. $\endgroup$ Jul 24 at 21:43
  • $\begingroup$ I'm using standard notation. $\endgroup$
    – Steven
    Jul 24 at 21:43
  • 2
    $\begingroup$ Michael Sipser. "Introduction to the theory of computation" 3rd edition. pp. 1-441. Cengage Learning. 2013. ISBN: 978-1-133-18779-0. $$\text{and}$$ Sanjeev Arora, Boaz Barak. "Computational complexity - A Modern Approach". pp. 1-543. Cambridge University Press, 2009. ISBN: 978-0-521-42426-4. $\endgroup$
    – Steven
    Jul 25 at 0:02
1
$\begingroup$

Take $B=\Sigma^*$. Obviously, $A\setminus B=\emptyset$ is not NP-complete. I'm not sure how concatenation has anything to do with set subtraction, but obviously, concatenating $B=\Sigma^*$ to $A\setminus B=\emptyset$ won't yield $A$ back, since $\Sigma^* \emptyset=\emptyset$ as $\emptyset$ doesn't contain any words.

$\endgroup$
2
  • $\begingroup$ My argument does not concatenate sets, and I don't know what you mean by the word "substruction" at all. Also, I don't know what you mean by "Σ∗". $\endgroup$ Jul 24 at 22:46
  • 2
    $\begingroup$ $\Sigma^*$ is the set of all possible words. If you don't know what set subtraction is, maybe you want to consider learning a bit of set theory before. Just the basic stuff: union, intersection, subtraction, etc. will be enough. About the concatenation, what exactly did you mean by that? What do you concatenate? $\endgroup$
    – nir shahar
    Jul 25 at 0:17
1
$\begingroup$

Your algorithm $Z$ doesn't decide $A$. If the input is in both $A$ and $B$, then it returns "no" even though the correct answer is "yes." The error can't be fixed, since it's generally impossible to deduce whether an input is in $A$ if you only know its membership status in $B$ and $A \setminus B$.

$\endgroup$

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.