3
$\begingroup$

I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is:

\begin{equation} 3SAT \leq_p KCLIQUE \end{equation}

I am really trying to understand everything formally -- putting everything in a strict logical notation helps me learn Math. To clarify, the content of this proof, has not helped me give other reductions because I don't understand one direction of the $\iff$ in the logic of reductions.

In this reduction, $f$ must be s.t: \begin{equation} w\in 3SAT \iff f(w) \in KCLIQUE \end{equation} and $f$ computes within a polynomial number of steps of the input size. The polynomial part is easy for me to understand, so no problem here!

I see that the above logical statement is equivalent to: \begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land w\not\in 3SAT \implies f(w) \not\in KCLIQUE\end{equation} The above just says yes-instances map to yes-instances and no-instances map to no-instances.

It appears that Sipser shows us: \begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land f(w) \in KCLIQUE \implies w\in 3SAT\end{equation}

Which is also equivalent to the above by taking the contrapositive of the second implication.

Here is my understanding of the $\implies$ direction. Given a yes-instance of $3SAT$, show that the reduction $f$ gives us a yes-instance for $KCLIQUE$. This seems completely natural.

I don't really understand the other direction -- namely, given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of $3SAT$. However since the reduction goes from $3SAT$ to $KCLIQUE$ i.e. the domain is the language $3SAT$ and the Codomain is the language $KCLIQUE$, I don't understand how we show this.

It appears that the argument is; Our reduction has provided us this graph, from which we can create a satisfying assignment from?

Please help me understand the other direction, and thanks for your time.

$\endgroup$
4
$\begingroup$

Your problem may be a slight misunderstanding.

Given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of 3SAT.

This is almost correct; check the claimed equivalence again:

$\qquad\displaystyle w \in \mathrm{3SAT} \iff f(w) \in \mathrm{KCLIQUE}\;. \tag{1}$

For the "backwards" direction, you only need to assume a yes-instance from the intersection of the image of $f$ and KCLIQUE, i.e. show that

$\qquad\displaystyle \forall w \in \operatorname{img}(f) \cap \mathrm{KCLIQUE}.\ f^{-1}(w) \in \mathrm{3SAT}$.

That means that you can assume some structure about the instances you need to prove the reverse direction for, namely that introduced by your reduction.

Another misunderstanding:

the domain is the language 3SAT and the Codomain is the language KCLIQUE

That's not true; note that (1) is (maybe implicitly) supposed to hold for all $w \in \Sigma^*$, that is the domain of $f$ is $\Sigma^*$. All $w \not\in \mathrm{3SAT}$ must therefore map to $f(w) \not\in \mathrm{KCLIQUE}$ in order to fulfill (1), so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.

$\endgroup$
  • $\begingroup$ Are you missing an implication in the statement to read like: $\forall w\in img(f) \cap KCLIQUE \implies f^{-1}(w) \in 3SAT$ $\endgroup$ – CodeKingPlusPlus Mar 25 '14 at 11:54
  • $\begingroup$ No. What you mean is $\forall w\in \Sigma^*. \operatorname{img}(f) \cap \mathrm{KCLIQUE} \implies f^{-1} \in \mathrm{3SAT}$ but that's equivalent to what I wrote (scope restriction on $w$ by quantifier range vs explicit by implication). $\endgroup$ – Raphael Mar 25 '14 at 12:00

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.