What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.