Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?
Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is at least in $NP$ because the following algorithm can always be given:
Co-P(J):
bool res = P(J)
return !res
Where $Co-P(J)$ is the algorithm solving $Co-P$ and $P(J)$ is the nondeterministic polynomial algorithm solving P.
Why is this not correct?
A problem is in NP if for all instances where the answer is “Yes” you can guess a hint and verify it in polynomial time. Nothing at all is said for instances where the answer is “No”. That distinction between “Yes” and “No” answers is essential.
What your proof attempt shows is that if a problem X is in NP, then the co-problem “Does X have the answer ‘No’” is in co-NP, as we would expect, and says nothing about NP.
The problem with your proof is the fact that a TM for $NP$ would be non-deterministic.
The non-determinism allows the machine to split up into branches of computation, and your machine will accept iff there is a branch in which the computation accepted.
In order to know whether on an input the machine did not accept, you would have to know whether for every branch it did not accept.
Switching the result from a non-deterministic TM is pretty much like swapping between $\exists$ and $\forall$ and checking $\forall$ is a totally different problem than checking $\exists$.
I hope this made sense to you! If not, try to think of $NP$ as polynomial verifiable languages, i.e languages with a machine $M(x,w)$ where $w$ is a "witness" describing the $\exists$, and then calling a routine for an NP problem means calling $M$ with the correct "witness" - but to know that the input $x$ is not in the language means to know that every "witness" is not a correct one
