1
$\begingroup$

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$. However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

But what if I try to reduce the language $ATM$ : {$(i,w)$ | $TM_i$ accepts $w$} to a well-known computable Turing-decidable language (i.e. $VERTEX-COVER$) using this function $f$:?

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

In this case, $f$ is computable, and if $(i,w) \in A$, then $f(i,w)$ = $g \in VERTEX-COVER$. Since many-to-one reductions do not have to be surjective, I do not have to map all elements in the vertex-cover set, and yet, $g$ meets the conditions of the many-to-one reduction. There is also no necessary condition for $f$ to have a 'pullback' function $\hat{f}$, where $\hat{f}$ is an 'inverse' that maps all elements in vertex-cover back to $ATM$ since $A \leq_m B$ does $\textbf{not}$ necessarily imply $B \leq_m A$. (the pullback function $\hat{f}$ holds only if $f$ is surjective, which is not necessary in $\leq_m$).

Given the lemma, if $A \leq B$ and $B$ is decidable, then $A$ is decidable. In this case, $VERTEX-COVER$ is decidable, then $ATM$ should be decidable... which is clearly wrong.

There is something obvious that I am missing here ...

$\endgroup$
  • 1
    $\begingroup$ Your understanding of many-one reduction is thoroughly wrong. ​ ​ $\endgroup$ – user12859 Sep 14 '17 at 3:34
  • $\begingroup$ in the surjective part of many-one reductions? $\endgroup$ – Link L Sep 14 '17 at 3:47
  • 2
    $\begingroup$ No. ​ The initial thing I noticed was that you have the quantifiers in the wrong order. $\hspace{1 in}$ The next thing I noticed ​ (although this change wouldn't matter if you don't also make my next sentence's change) ​ is that you're missing $\;\;\;\;\;\;\;$ "$\;\;\; x\in A \: \iff \;\;\;$" $\;\;\;\;\;\;\;$ before $\;\;\;$ "$\; f(x) \in B\;$" $\;\;\;$ . $\hspace{1 in}$ The last thing I noticed is that your universal quantifier is only over elements of $A$ rather than over elements of ​ $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.04 in}\}^{\hspace{-0.02 in}*}$ . $\hspace{2 in}$ $\endgroup$ – user12859 Sep 14 '17 at 4:15
2
$\begingroup$

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$.

No. It's not "for each element $x\in A$ there exists a computable $f$ ...", but "there exists a computable total $f$ s.t. for each $x\in A$ we have $x \in A \iff f(x) \in B$".

Your definition is wrong because:

  1. it allows us to pick a different function for each $x\in A$, when we must pick only one;
  2. it only states $x\in A \implies f(x)\in B$, when we need the double implication $\iff$;
  3. $f$ must be total (maybe this is supposed to be implicit when you don't say "partial", but it's important)

However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

Correct.

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

How do you check that TM $i$ accepts $w$? I guess you are simply suggesting to simulate TM $i$. If you do that, there is a possibility of non termination here: precisely, every time $i$ diverges. Hence, $f$ is not total in this case: since its implementation diverges on some inputs.

$\endgroup$
  • $\begingroup$ But hasn't it been done a lot of times (i.e. Sipser's textbook on Complexity) that instances $(i,w)$ of$ATM$, (where $ATM$ is the set where $TM$ $i$ accepts $w$) are reduced (simulated) to instances of another set such as $HALT_{TM}$ or $REGULAR_{TM}$. Here, they assumed that $x \in ATM$ and that a $TM$'s inherent possibility of looping is not a factor to consider - since the domain is already in $ATM$ and $f$ is meant to halt. $\endgroup$ – Link L Sep 14 '17 at 9:29
  • $\begingroup$ @LinkL No, it is a possibility to consider IF you actually run that TM. It is not to be considered if given a TM $M$ the function returns another TM $N$, where $N$ simulates $M$ internally. This is a big difference, since in such case the function does not need to run $M$ to produce $N$. You can compare to this: a compiler takes a program as input (say, in C) and produce another program as output (e.g. in assembly). The compiler will halt even if the C program diverges, so that's OK, and can be used for a reduction. If we used an interpreter which actually runs the program, we could diverge. $\endgroup$ – chi Sep 14 '17 at 10:52
  • $\begingroup$ That makes a lot of sense. $\endgroup$ – Link L Sep 16 '17 at 1:00
1
$\begingroup$

Your function $f$ has to be computable, meaning $f(x)$ must be defined for all $x\in \Sigma^*$, such that $x\in ATM \text{ iff } f(x) \in VC$. But you don't describe how you are going to map $x$ to $VC$, which of course is impossible. In other words you still need to decide if $x\in ATM$ before you map $x$ into $VC$.

$\endgroup$
  • $\begingroup$ Thanks, but what if a Turing machine M is 'inside' $f$, such that it outputs a valid VC element $g$ iff $(i,w) \in ATM$ ? $\endgroup$ – Link L Sep 14 '17 at 3:45
  • $\begingroup$ Then ATM would be decidable. But, you know ATM is not decidable and so such TM computing $f$ does not exists. Again, you don't provide a TM computing $f$. So, can't deduce $f$ is computable. $\endgroup$ – fade2black Sep 14 '17 at 3:50

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.