Cheap and Secure Web Hosting Provider : See Now

[Solved]: Implications of polynomial time reductions

, , No Comments
Problem Detail: 

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?

Asked By : Ryan M

Answered By : Syzygy

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.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback