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 $xin P$, then you have proof that $Piin 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 $xin 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 : http://cs.stackexchange.com/questions/7438 Ask a Question Download Related Notes/Documents
