I just started to learn the complexity theory, and I have a simple question:
Let's say that there's a language B in NP, such that there's no polynomial reduction from B to a given language A (which is in P).
Can I conclude from this that B is not in P? why?
It is the case that for any two languages $A$ and $B$, both in $P$, there is a polynomial-time reduction from $B$ to $A$. (Except when $A$ is a trivial language, either the empty set, or the set of all strings.) (Details are below.)
This being the case, if $B$ was in $P$, there would be a polynomial-time reduction to $A$ (unless $A$ was trivial).
So if there is no polynomial-time reduction from $B$ to $A$, then either $B$ is not in $P$, or $A$ is trivial.
To see that any language $B$ in $P$ is polynomial-time reducible to any nontrivial language $A$ in $P$, first recall what it would mean for $B$ to be polynomial-time reducible to $A$: Given an instance $I$, we could decide $I\in B$ by transforming $I$ to $I_A$ and deciding $I_A \in A$ instead.
The basic strategy is that since we can already decide membership in $B$ in polynomial time, we can perform a polynomial-time reduction to $A$ by doing some unimportant computation that reduces to $A$, then throwing that away, and then just deciding membership in $B$ directly. But here are the details.
Suppose $a\in A$ and $a'\notin A$. (These exist, because $A$ is nontrivial.) Then here is a polynomial-time reduction from $B$ to $A$:
This works for any $B$ and $A$ that are both in $P$, as long as there are $a$ and $a'$ as required. (If not, then $B$ is not polynomial-time reducible to $A$.)
(Related post: Reduction between languages in P)
