Simple question on complexity 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?
 A: 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$:


*

*Let $I$ be given.  We want to decide, in polymomial time, whether $I\in B$, by transforming $I$ to $I_A$ and deciding $I_A\in A$ instead.

*Since $B$ is in $P$, first decide (in polynomial time) if $I\in B$ or $I\notin B$.

*If $I\in B$, let $I_A = a$.  Otherwise, let $I_A = a'$.

*Then $I\in B$ if and only if $I_A\in A$, as required.


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)
