Implications of polynomial time reductions

Question

I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong.

I'm presented with a problem $\Pi$ of unknown complexity class. If I can transform $\Pi$ to some problem $X$, where $X \in {\sf P}$, what does that tell me about $\Pi$?

I think allows me to conclude that $\Pi \in {\sf P}$, right? If I can reduce $\Pi$ to another problem that's deterministically solvable in polynomial time, and the transformation itself can be done "easily" in polynomial time, then I can conclude that $\Pi$ is deterministically solvable in polynomial time, and therefore that $\Pi \in {\sf P}$ correct?

Conversely, given the same input, transforming $X$ to $\Pi$ in polynomial time allows me to conclude nothing meaningful, since nothing is known about $\Pi$ right?

Answer 1

In essence, you are right. Given a problem $\Pi$, if you can find a poly-time reduction from $\Pi$ to any problem $x\in P$, then you have proof that $\Pi\in P$ as well.

A reduction from problem $A$ to $B$ is basically a function that transforms any input of $A$ into an input of $B$, such that the solutions agree. That means, you can use any algorithm for $B$ to solve $A$.

For the second part, if you can reduce a problem $x\in P$ to $\Pi$, then $\Pi$ might be in $P$, or not. However, if you can find a way to reduce all problems in $P$ (or equivalently, some $P$-complete problem), then you have shown that $\Pi$ is $P$-hard.

Answer 2

Right, if you have an algorithm A that reduces $\Pi$ to $x$ in polytime, and you can solve $x$ is polytime using some algorithm B, then you can solve $\Pi$ in polytime by applying first A and then B.

Using polytime reductions on a problem in P however is rather boring, since you can solve the instance during the reduction and map every instance of $x$ to either a trivial yes or a trivial no answer. Normally you restrict yourself to logspace reductions for problems from P.