I am reading the reduction given by Sipser in his textbook \"Introduction to the

ID: 652890 • Letter: I

Question

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

egin{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: egin{equation} win 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: egin{equation} win 3SAT implies f(w) in KCLIQUE land w otin 3SAT implies f(w) otin KCLIQUEend{equation} The above just says yes-instances map to yes-instances and no-instances map to no-instances.

It appears that Sipser shows us: egin{equation} win 3SAT implies f(w) in KCLIQUE land f(w) in KCLIQUE implies win 3SATend{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.

Explanation / Answer

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:

$qquaddisplaystyle w in mathrm{3SAT} iff f(w) in mathrm{KCLIQUE};. ag{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

$qquaddisplaystyle orall 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 otin mathrm{3SAT}$ must therefore map to $f(w) otin mathrm{KCLIQUE}$ in order to fulfill (1), so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.

Navigate

I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a the

I am reading up on TEE in ARM. I am looking for pointers for the following quest

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I am reading the reduction given by Sipser in his textbook \"Introduction to the

Question

Explanation / Answer

Related Questions

Navigate