Does many-to-one reduction imply polynomial time reduction?

Question

We know that if $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. And we also know that if $A \le_m B$, then $A$ is many-to-one reduction to $B$.

Can we deduce that if $A \le_m B$ then $A \le_p B$?

Answer 1

Assuming the question is: "Suppose that $A$ is many-one reducible to $B$. Is $A$ polytime many-one reducible to $B$?"

The answer is no. The language $\{\Phi : \Phi\text{ valid boolean formula with quantifiers}\}$ is $\mathsf{PSPACE}$-complete (sometimes known as QBF or TQBF). One can many-one reduce this language to the language $\{(G,s,t) : G \text{ graph,} s,t\in G, \text{ there is a path from $s$ to $t$}\}$, which is in $\mathsf{NL}$ (called REACHABILITY, PATH, or the like). Given $\Phi$, the reduction tests if the formula is valid (in polynomial space). If it is, the reduction maps $\Phi$ to the edge graph $\{s,t\}$. Otherwise, the reduction maps $\Phi$ to the graph on 2 vertices $\{s,t\}$ with no edges.

However, no many-one reduction can be done in polynomial time, as per the Space hierarchy theorem, which entails that $\mathsf{NL}\subsetneq \mathsf{PSPACE}$.