Skip to main content
added 133 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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}$.$\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:true; note that (1) is (maybe implicitly) supposed to hold for all $w \in \Sigma^*$, that is the domain of $f$ is $\Sigma^*$; all. 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.

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}$.

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: the domain of $f$ is $\Sigma^*$; all $w \not\in \mathrm{3SAT}$ must map to $f(w) \not\in \mathrm{KCLIQUE}$, so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.

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.

Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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}$.

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: the domain of $f$ is $\Sigma^*$; all $w \not\in \mathrm{3SAT}$ must map to $f(w) \not\in \mathrm{KCLIQUE}$, so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.