3
$\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$

4 Answers 4

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

$\endgroup$
2
$\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.

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

$\endgroup$
1
  • $\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_
    Commented Jul 13, 2020 at 15:21
0
$\begingroup$

Three years late to the thread but here's another from a Turing Machine perspective:

Defining NP with NTMs and showing that certificate/verifier implies membership of NP

We define $NP$ as the set of decision problems that can be solved in polynomial time by a nondeterministic Turing machine (NTM). We can show that a decision problem $X$ (such as $\text{SAT}$) is a member of $NP$ if the following conditions are satisfied:

  • For each "Yes" instance $w$, there exists a binary string $C_w$ that serves as proof that indeed $w\in X$. We require that $|C_w|=p(|w|)$ where $p(x)$ is some polynomial. In the case of $\text{SAT}$, $w$ encodes a boolean formula $\phi$ on $n$ boolean variables $x_1,x_2,\ldots,x_n$, and $\phi\in\text{SAT}$ if and only if there exists a truth assignment of the variables which results in $\phi$ evaluating to true. A straightforward choice of $C_w$ would then be an encoding of that truth assignment, and $|C_w|$ would then be linear in $|w|$ because you only need one bit for the truth assignment of each boolean variable.
  • There exists a deterministic, polynomial time algorithm $\text{verifyX}(w,C)$ that uses $C$ to confirm that $w\in X$. This is to say, if argument $C$ is sufficient proof that $w\in X$, $\text{verifyX}()$ accepts, otherwise it rejects. In the case of $\text{SAT}$, this algorithm would simply plug the assignment $C$ into the boolean formula $\phi$ and accept if and only if $\phi$ evaluates to true.

Given these two conditions, we can construct a nondeterministic Turing machine that decides decision problem $X$ by implementing the following algorithm:

$ \text{NPDecideX}(w)\\ 1.\text{ initialize }C[1,\ldots,p(|w|)]\\ 2.\text{ for }i\gets 1\text{ to }p(|w|)\\ 3.\quad\quad \text{nondeterministically choose }c\in\{0,1\}\\ 4.\quad\quad C[i]\gets c\\ 5.\text{ return verifyX}(w,C) $

This algorithm essentially just nondeterministically chooses the entire certificate $C$ one bit at a time and then uses $\text{verifyX}$ using said certificate $C$. It works in polynomial time because it takes $p(|w|)$ iterations to choose $C$, then a polynomial amount of time to verify $w$ using $C$.

"An NTM accepts an input string if and only if at least one of the possible computational paths starting from that string puts the machine into an accepting state."

So on input $w\in X$, our NTM accepts because there exists a path it could take where $\text{verifyX}()$ accepts, namely the path where $C_w[i]$ is chosen on the $i^{\text{th}}$ iteration for all $i$. On input $w\notin X$, our NTM rejects because there does not exist a certificate $C_w$ which proves $w\in X$, thus no such path can exist where $\text{verifyX}()$ returns true.

All of this is to say we've constructed an NTM that decides $X$ in polynomial time, thus $X\in NP$ by definition. In short, certificate-verifier $\implies X\in NP$. The Cook–Levin theorem tells us that the reverse implication also holds, but we don't have to get into that here.

We can't easily show SAT is in CoNP

So let's say we construct an NTM $M$ that decides SAT using this certificate-verifier method. What happens if we construct a new machine $M'$ by negating the output of $M$?

$ \text{NPDecideXbar}(x)\\ 1.\text{ initialize }C[1,\ldots,p(|w|)]\\ 2.\text{ for }i\gets 1\text{ to }p(|w|)\\ 3.\quad\quad \text{nondeterministically choose }c\in\{0,1\}\\ 4.\quad\quad C[i]\gets c\\ 5.\text{ return NOT}(\text{verifyX}(w,C))\quad // \gets \text{We added a NOT}()\text{ here} $

The question is, does the resulting machine then decide $\overline{\text{SAT}}$? Well, no. Here's why:

Let's consider a nontrivial "Yes" instance $w$. By nontrivial I mean not all possible certificates $C$ work to prove that $w\in X$, but at least one does. In the case of SAT, $w=\phi=x_1\vee \neg x_1$ would be trivial because any truth assignment results in $\phi$ evaluating to true. Conversely, $w=\phi=x_1$ is a nontrivial "yes" instance because assignment $x_1$=true makes $\phi$ evaluate to true but assignment $x_1=$false makes $\phi$ evaluate to false.

The key is to realize that not only does $M$ accept $w$ because $w\in X$, but also $M'$ accepts $w$ because there exists a computational path where $M'$ ends in a halt-accept state, namely one where an invalid certificate is chosen, thus $\text{verifyX}(w,C)$ returns false and $\text{NOT}(\text{verifyX}(w,C))$ returns true. This is to say $M'$ accepts $w\in X$ and $w\notin \overline{X}$ so $M'$ does not decide $\bar{X}$. Our nondeterministic turning machine $M'$ doesn't decide $\overline{\text{SAT}}$ (i.e. the language of all boolean formulas $\phi$ which are unsatisfiable), rather it decides the language of all boolean formulas $\phi$ which are not trivially satisfiable, which includes many formulas that are satisfiable.

This is not to say that $\text{SAT}\notin CoNP$. We didn't show that there doesn't exist a NTM that decides $\overline{\text{SAT}}$ in polynomial time, we just showed that our nondeterministic machine $M'$ doesn't work. Hypothetically, if one were to show that for every unsatisfiable boolean expression $\phi$, there exists a way to certify that indeed $\phi$ is unsatisfiable using a certificate of polynomial size, and there also exists a deterministic polynomial time algorithm which verifies that $\phi$ is indeed unsatisfiable given said valid certificate, then that person would have shown that indeed $\overline{\text{SAT}}\in NP$ and thus $\text{SAT}\in CoNP$. However, that would not at all be easy to show and that's evidenced by the fact that at the time of writing this, it's still an unsolved problem in computer science.

$\endgroup$

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.