8
$\begingroup$

I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every problem in coNP can be reduced to $\text{TAUT}$ in polynomial time. To do that, I would need one of two things:

  1. A known coNP-complete problem for reduction or
  2. a proof that a problem is coNP-complete if its complement is NP-complete.

Neither of these was given to us in lecture, so I cannot use anything without proving it myself. Did I miss anything which should have been obvious? Where should I start?

$\endgroup$

1 Answer 1

10
$\begingroup$

I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general).

The answer of your questions easily follows from the definition of $coNP$. Remember that a language $L \subseteq \{0,1\}^*$ is in $coNP$ is $\bar{L} = \{x \in \{0,1\}^* \mid x \notin L\} \in NP$. For example, $\overline{TAUT}$ is the set of DNF that are not a tautology. To prove that a DNF is not a tautology, you only have to find an assignment that does not satisfy your formula, which can be done in polynomial time with a NTM (just "bruteforce" the assignments). Hence, it is in $NP$. In other words, $\overline{TAUT} \in NP$ thus $TAUT \in coNP$.

Now take an $NP$-complete language $L$. By definition, $\bar{L} \in coNP$. We show that $\bar{L}$ is $coNP$-complete, that is, for every language $A \in coNP$, $A \leq \bar{L}$. Let $A \in coNP$. Then $\bar{A}$ is in $NP$. By $NP$-completeness of $L$, there exists a function $f$, computable in polynomial time such that $x \in \bar{A}$ iff $f(x) \in L$. This is equivalent to say that $x \notin \bar{A}$ iff $f(x) \notin L$. Which in turn, is equivalent to $x \in A$ iff $f(x) \in \bar{L}$. Thus, $f$ is also a reduction from $A$ to $\bar{L}$, meaning that $A \leq \bar{L}$. In other words, $\bar{L}$ is $coNP$-complete.

Now, if you want to show that $TAUT$ is $coNP$-complete, you only have to show that $\overline{TAUT}$ is $NP$-complete. And it is not hard to see that $SAT \leq \overline{TAUT}$. Indeed, a CNF $F$ is satisfiable iff $\neg F$, which is a DNF, is not a tautology.

$\endgroup$
1
  • $\begingroup$ Could you have a look at this question? Just in case you got some time and will to help me out here. I already tried to do it similarly to this problem but failed when it came to the reduction functions as there are no complements involved. $\endgroup$ Jun 9, 2017 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.