Is it always possible to have one part of the reduction?

Question

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.

Answer 1

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.