patternMinor
Polynomial Reduction 3SAT to K-Clique
Viewed 0 times
reductionclique3satpolynomial
Problem
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.
\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.
Solution
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.
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.
Context
StackExchange Computer Science Q#23030, answer score: 4
Revisions (0)
No revisions yet.