Can polynomial many-to-one reduction be done to a specific problem instance?

Question

Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given some polynomial time algorithm for $B$, I just have to transform $A$ to $B$ and solve $B$. So it can be thought as:

The reduction must be done from arbitrary instance of $A$ to a legal instance of $B$

My question is, do I have to reduce to arbitrary instance of $B$ or some instance of $B$? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.

Answer 1

The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if the original problem was an accepting instance, or the rejecting instance if the original problem was a rejecting instance.

That said, the Berman–Hartmanis conjecture states that all NP-complete problems are polynomial time isomorphic, meaning that there is a bijective polynomial-time many-one reduction between them with a polynomial-time inverse. This is currently an unproven conjecture, and only refers to NP-complete problems.