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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top