1
$\begingroup$

So I have been asked this question during my comprehensive and I have a few answers to it, I just wanted to check with the community whether I'm on track with them.

Is the following statement true?

$\forall A,B \subseteq \Sigma^{*}, \exists\ f : \Sigma^{*} \rightarrow \Sigma^{*}, s.t. \forall x \in A \implies f(x) \in B $

The function $f$ had to be decidable in polynomial time, as in the notion of reductions. So, the question in english stands as, is it always possible to find a polytime computable function of the like written above, for any two languages, s.t. one direction of the notion of reduction holds.

So, at that moment I couldn't argue for polytime computability, but , the obvious idea of having a map from $\Sigma^{*}$ to an element in B, was all I could come up with. Later, on subsequent thinking I realised that it basically becomes a membership checking question for arbitrary B. Another idea, also struck and that being when B $\ =\ \phi$, then $(A,\phi)$ serve as the counterexample sought, where A is any language.

So, in case we do not allow for B being the empty language, any instance of B which is undecidable or rather, takes more than polynomial time for membership checking [Not sure about the second one as its unknown whether P!=NP] holds, right?

Other questions associated to this, are:

(1) if A=3SAT and B $\in \mathbb{P}$ , then does the existence of such a $\ f$, prove P=NP or do you need the reverse direction of reduction to hold as well, to conclude that?

(2) What about when $\ f$ is allowed to be decidable, or semidecidable, what changes?

(3)And, what if the reverse direction of reduction was the condition to be satisfied by $\ f$, ie, $\forall x \in \Sigma^{*},\ f(x) \in B \implies x \in A$ then what changes? [ I worked this out, taking the contrapositive , ie, $\forall x \not\in A \implies f(x) \not\in B$ it basically boils down to membership checking for the complement language, ie, $\overline{B}$ ]

EDIT : Sorry (1) was trivial. As pointed out by the answer below, $\mathbb{P} \subseteq \mathbb{NP}\ $ means I can just use the same f trivially for the reverse direction.

$\endgroup$
  • 1
    $\begingroup$ It is meaningless to say $f$ is decidable since it is a function. Sets/languages may be decidable or their characteristic functions $\psi: \Sigma^* \rightarrow \{0,1\}$ may be decidable. So do you mean $f(x) \in B$ is decidable? $\endgroup$ – fade2black Jul 24 '17 at 9:49
  • $\begingroup$ I might have mixed up definitions, but I think my major goof was, I do consider functions as sets, because they are just special kind of relations. Is it that a proper distinction is made for decidability that we only speak of sets that are not functions? What about a synthetic problem like deciding whether a given relation (set) between finite sets A and B is an injective function or not? $\endgroup$ – Ramit Jul 24 '17 at 10:45
  • 1
    $\begingroup$ Basically, decidability establishes a relationship between effective computation (TMs) and a set $S$, namely, the question if $x \in S$ can be answered 'yes' or 'no' by a TM or a computer in a finite amount of time. However, $S$ may be any set. If you $S$ is a set of pairs $<x,y>$ then it may be a function or a relation. So if $x$s are in $A$ and $y$s are in $B$ then the set $S$ may be interpreted as a relation/function between $A$ and $B$. Then depending on the set $S$ it may be decidable or not decidable. $\endgroup$ – fade2black Jul 24 '17 at 11:17
  • 1
    $\begingroup$ As for the second question, how could we represent the set of pairs of sets: $<A, B>$? Only if we had two countable sets of sets $S=\{A_1, A_2,\dots \}$ and $T=\{B_1, B_2,\dots \}$ then we could define a set $INJ=\{<i,j> | \text{ there is injection from } A_i \text{ to } B_j \}$ and decide if $<x,y> \in INJ$. $\endgroup$ – fade2black Jul 24 '17 at 11:47
  • $\begingroup$ For example you could enumerate all recursively enumerable sets, for example each r.e. set may be associated with its TM's index that computes that set. Then you could ask questions about the pairs of sets. $\endgroup$ – fade2black Jul 24 '17 at 12:10
1
$\begingroup$

If you define "reduction" using a single implication as in $x\in A \implies f(x) \in B$, then $A$ indeed always "reduces" to any nonempty $B$. Take any $b\in B$, and define $f(x)=b$ the be a constant function. This is computable in O(1), hence in polytime.

It does not matter if $B$ is decidable, or in P, or anything else -- as long as it is not empty, that's enough.

1) No, it does not prove anything. If you have that $A$ reduces to a PTIME $B$ with your proposed reduction, you can't conclude $A$ is PTIME. $HALT$ would reduce to checking if a number is $12$ (which is PTIME), but $HALT$ is surely not PTIME.

2) $f$ above is constant, hence always decidable. (There is no such a thing as a semicomputable function)

3) Similarly, the converse implication is satisfied, for any $A$ and non-full $B$, if we take the constant function $f(x)=b \notin B$.


Below, I consider the more standard definition of reduction with the double implication.

The halting problem is not reducible (polytime or not) to its complement, nor its complement is reducible to the halting problem.

This is because $A\leq B$ holds iff $\bar A \leq \bar B$, hence in either case the complement of $HALT$ would reduce to $HALT$, but the first is not recursively enumerable, and the second is, so we get a contradiction.

For the others:

1) Yes. The reverse direction is trivial, since if $B\in P$ then $B\in NP$ hence it reduces to 3SAT.

2) The $HALT$ counterexample above holds for any computable $f$. There is no such a thing as a semicomputable function -- semidecidability only applies to problems.

$\endgroup$
  • 1
    $\begingroup$ But I still have a doubt about the proof like choosing HALT and its complement. While reducibility requires two sided implication, the OP requires only one sided implication. Any idea? $\endgroup$ – fade2black Jul 24 '17 at 10:37
  • $\begingroup$ Yes exactly same confusion here! $\endgroup$ – Ramit Jul 24 '17 at 10:48
  • $\begingroup$ @fade2black Ah! I guess I overlooked that, good point! $\endgroup$ – chi Jul 24 '17 at 11:29
  • $\begingroup$ I expanded (3), hope it is clear now. Regarding (2) my bad for extending the notion to functions! The point you make about fixing any b $\in B$ is what I was referring to as the membership checking problem, since B might just come with a short description, and I need to check over words in $\Sigma^{*}$ whether any one of them belongs to B. $\endgroup$ – Ramit Jul 24 '17 at 15:05

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.