1
$\begingroup$

I am trying to understand the definition of the complement of a decision problem.

The reason is because it is the core issue that is stopping me from understanding why SAT is the complement of TAUTOLOGY (a statement that is made in my Discrete Mathematics lecture notes).

My lecture notes also state that the definition of the complement of a decision problem is as follows: the complement of a decision problem $X$ is the same problem with the yes and no answers reversed.

The full problem can be found in my question here, if it helps. (I have asked this new SE question, because the previous question was becoming potentially too long, and I have managed to narrow it down to this core issue of the definition of the complement of a decision problem, I think.)

Help would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Your lecture notes seem to be reversing TRUE and FALSE in addition to reversing yes and no answers. $\endgroup$ – Doug Chatham Oct 13 '16 at 18:36
  • $\begingroup$ @DougChatham That's exactly what I thought when poring over them, trying to understand the logic! I might contact my lecturer. $\endgroup$ – Caleb Owusu-Yianoma Oct 13 '16 at 18:43
  • $\begingroup$ @Rodrigo: Thanks! $\endgroup$ – Asaf Karagila Feb 21 at 7:46
2
$\begingroup$

A "decision problem" is usually defined to be a subset $P$ of some given set $L$ (which I will refer to as a "language"), whose elements can be represented in some agreed way as inputs to a Turing Machine (or inputs to a partial recursive function or some other equivalent model of computation - I will stick with Turing Machines). The decision problem given by $P$ and $L$ is decidable if there is a Turing Machine that, given any element $\phi$ of $L$ on its input tape will terminate, writing $Y$ on its output tape if $\phi \in P$ and writing $N$ on its output tape otherwise.

So for example for SAT and TAUTOLOGY, the language $L$ is the set of all propositional formulas. SAT is the subset of $L$ comprising the satisfiable formulas (those that can be made true by some assignment of truth values to propositional variables). TAUTOLOGY is the subset of $L$ comprising the tautologies (those formulas that are true under any assignment). The method of truth tables shows that both SAT and TAUTOLOGY are decidable (as decision problems in the language $L$).

The phrase "complement of a decision problem" is not a standard technical term, but it has an obvious informal interpretation in terms of complementation of subsets of the language $L$. This interpretation does not assume anything about the internal structure of $L$ (other than the agreed representation of elements as $L$ as inputs to a Turing Machine).

In the case of SAT and TAUTOLOGY, the language $L$ has some internal structure that includes the negation operation: $P \mapsto \lnot P$. A formula $P$ is in the complement of SAT iff the negation ($\lnot P$) of $P$ is in TAUTOLOGY. To say SAT is the complement of TAUTOLOGY is understandable but wrong - the complement of SAT comprises the formulas that are false under every assignment. The negation operation on formulas is a bijection between the complement of SAT and TAUTOLOGY, but TAUTOLOGY is not the complement of SAT.

$\endgroup$
  • $\begingroup$ Excellent answer. That clears up everything. $\endgroup$ – Caleb Owusu-Yianoma Oct 14 '16 at 17:22

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.