Polynomial Time reducible explanation
-
05-11-2019 - |
题
Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct?
If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in P$ is false
I think this means that since $Y$ is not polynomial time solvable, and it is reducible to $X$, then X is not polynomial time reducible. This makes sense to me, but the statement ends with a false, how is that?
If $Y \leq_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well
Seems pretty intuitive, if you can reduce to $Y$ using a polynomial reducer, then it should also be solvable in constant time. But I have the nagging feeling that it wouldn't be constant time since polynomial time > constant time.
Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq_p X$
I don't get this at all, how can the $SORT$ algorithm be reducible to all $X$, isn't that a bit too farfetched?
Assume $Y \leq_p X$, if $Y$ doesn't have a polynomial time algorithm to solve it, then there isn't one for $X$ either
I think this implies that since $Y$ is not solvable in polynomial time then neither is $X$, but isn't that false? Isn't the whole purpose of us using reductions is to show that we can reduce one to another that already has a solution, thus translating the solution?
没有正确的解决方案