2
$\begingroup$

I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).

But I'm missing why the following machine doesn't turing recognize the complementary of SAT:

Given a turing machine M that recognizes SAT, the following turing machine recognizes coSAT:

  1. Run M on the input word w.
  2. If M accepts - reject.
  3. If M rejects - accept.

Because coSAT is the language of all unsatisfiable formulas, a formula is unsatisfiable if it doesn't have a satisfiable interpretation, which is exactly the opposite of what M outputs.

What am I missing in here?

$\endgroup$
1
$\begingroup$

You are missing a major part of the definition of $CoNP$: you need a proof that your machine $M$ runs in nondeterministic polynomial time for all "yes" inputs. Because you have simply taken the NP SAT algorithm and flipped it, it runs in nondeterministic polynomial time for all "no" inputs. But we have no such guarantees for the "yes" inputs.

The real answer is, nobody knows that SAT isn't in $CoNP$. If we knew that, we would know that $CoNP = NP$, but this is still an open problem. So, nobody can point to a specific reason that you can't build a machine that decides the complement of SAT it nondeterministic polynomial time. It's just that nobody has been able to do it yet, or prove that it's impossible.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

So far as we know, NP and co-NP are separate complexity classes under Karp reduction, aka many-one polynomial-time reduction. Your procedure is a Turing reduction, not a Karp reduction. Turing reductions are too powerful for NP and co-NP to be separate classes under them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You're right, but I think it's possible his intention was not to show a reduction, but rather to construct a non-deterministic TM (equivalent to having a witness) that will show the language is in $CoNP$. Ofcourse it'll fail, due to the reasons stated above in the other answers. $\endgroup$ – Eric_ Jul 13 at 15:21
1
$\begingroup$

Always remember that for questions involving NP, instances with a "Yes" answer are treated totally different from instances with a "No" answer. Basically, a problem is in NP if any instance with a "Yes" answer can be proven to have the answer "Yes" in polynomial time, as long as we are able to make a fantastically lucky guess to help us. But instances with a "No" answer - no idea how to prove the answer is "No".

Your Turing machine solves SAT in the slow way, without using that lucky guess. For example, in exponential time by trying out all possible combinations of inputs for the SAT problem. And you're right, based on this Turing machine, we can build another one that solves the opposite of SAT in the exact same exponential time. But that doesn't prove that either is in NP or co-NP:

To be in NP, you'd need a Turing machine that doesn't just solve SAT in exponential time. You'd need one that starts by writing a fantastically lucky hint on the tape, and then using the hint and the SAT problem, finds out that the SAT instance can be solved, and all that in polynomial time - as long as the answer is Yes. If you just reuse this turing machine to solve co-SAT, it would find solutions quick if the answer to the original SAT problem is "Yes", and therefore the answer to the co-SAT problem is "No". But that doesn't help: We need a Turing machine that can solve co-SAT problems with the answer "Yes" or equivalent, SAT problems with the answer "No", and we don't have that.

| cite | improve this answer | |
$\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.