if A is in P and B is NP, then is A polynomial time reducible to B?
Could anyone prove a prove or disprove for it?
$\begingroup$
$\endgroup$
If $B$ is neither empty nor the universal set, then the reduction can be performed and is trivial.
You need to have two strings $w_1 \in B$ and $w_2 \notin B$. In the reduction of membership problem $(A,x)$, we trivially solve the membership in $A$ in polynomial time: if $x \in A$ then return $w_1$ else $w_2$.
$\begingroup$
$\endgroup$
Assuming you're talking about polynomial-time many-one reductions (i.e., Karp reductions), the claim is false. Consider the binary alphabet, let $A = \{0,1\}^*$ and $B=\emptyset$. Clearly $A$ is in $\mathsf{P}$ and $B$ is in $\mathsf{P} \subseteq \mathsf{NP}$, yet $A$ is not Karp-reducible to $B$.
