1
$\begingroup$

I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?

$\endgroup$
3
$\begingroup$

They are not precisely the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has only formulas that are not satisfiable.

In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a poly-time reduction from $\overline{SAT}$ to $UNSAT$ and vice versa.

$\endgroup$
1
  • $\begingroup$ Thanks man! great answer, simple and clear!! $\endgroup$ – ChaosPredictor Feb 10 at 15:32

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.