1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ @D.W. It occurs to me this post is a good example of how questions should be asked. First, it asks about conceptual issues about polynomial-time reduction. The question tells how OP thoughts about the examples. It is hard for me to raise a question better than this post had I have the same thoughts as OP, which could be quite possible when I first learned that concept. Could you? Second, all questions are tightly related to that one small concept. It is reasonable to put them together in one post. In fact, I believe it is better to put them together, more or less like our reference questions. $\endgroup$ – Apass.Jack Mar 19 at 1:01
  • $\begingroup$ I'm not seeing it -- it still looks like 4 different questions to me. The first is about understanding what it means to say that some property is false; the second is about the difference between polynomial time and constant time; the third about intuition regarding whether it's reasonable to imagine reductions from SORT to everything; and I'm not sure what the fourth is about. But OK, I've removed my comments, given that you feel that way. $\endgroup$ – D.W. Mar 19 at 4:45
1
$\begingroup$

What is polynomial-time reduction?

Let us recall the definition of polynomial-time reduction (function) as presented in section 34.3, NP-completeness and reducibility CLRS, third edition.

Let $\Sigma=\{0,1\}$. A language $L_1$ over $\Sigma$ is polynomial-time reducible to a language $L_2$ over $\Sigma$, written $L_1 \le_p L_2$, if there exists a polynomial-time computable function $$f: \{0, 1\}^*\to\{0,1\}^*$$ such that for all $x\in \{0,1\}^*$, $$x\in L_1\Longleftrightarrow f(x)\in L_2.$$ We call the function $f$ the reduction (function), and a polynomial-time algorithm $F$ that computes $f$ is a reduction (algorithm).

Examples

[FALSE]$\ \ $ If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.

What is $O(2^n)$? It is not $\Omega(2^n)$! For example, a constant function is in $O(2^n)$. If set $Y$ can be solved in constant time and $Y \leq_p X$ then $X$ can be in $\bf{P}$. For example, we can let $X=Y$.

[FALSE]$\ \ $ If $Y\le_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well.

You cannot ignore the time spent in the reduction step. $Y\le_p X$ tells us that it takes no more than polynomial time to map (a.k.a. reduce) an instance (a.k.a a word) of $Y$ to an instance of $X$. That polynomial time, as you suspected, is significant.

In fact, the complexity class $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$ for some $X$ that is solvable by constant time.

[ALMOST TRUE]$\ \ $ Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq_p X.$

There is a polynomial-time computable function $f$ that maps a word in $\{0,1\}^*$ that encodes a sorted list of ints to 1. Basically, we can use an algorithm that checks each int in the list is not greater than than the next int in the list. This algorithm is, in fact, linear-time.

Suppose word $x_0\not\in X$ and $x_1\in X$. Let $g$ be a function that maps 0 to $x_0$ and 1 to $x_1$. $g$ can be computed by a constant-time algorithm, since both $x_0$ and $x_1$ are fixed sequences of 0s and 1s. $g\odot f$ is a polynomial reduction from $SORT$ to $X$.

As long as $X$ is not the empty set nor the set of all words over $\Sigma$, $SORT \leq_p X.$

If $X$ is empty set, there is no reduction of any kind. If $X$ is the set of all words, then any map to $X$ will map any instance, including a "no" instance to a "yes" instance of $X$. Because of these two exceptions, we can say the proposition is false.

[TRUE]$\ \ $ 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

$Y \leq_p X$ implies
$\quad X$ is solvable in polynomial time $\Longrightarrow$ $Y$ is solvable in polynomial time.
Note that contrapositive of that implication is exactly
$\quad Y$ is not solvable in polynomial time $\Longrightarrow$ $X$ is not solvable in polynomial time.

Exercises

Check whether the following propositions are true.

Proposition 1. If set $Y$ can be solved in $\Omega(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.

Proposition 2. If set $X$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $Y \not\in \bf{P}$.

Proposition 3. If set $X$ is solvable by polynomial time, then $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$.

$\endgroup$
  • $\begingroup$ Just clarification on the first one, in my question I said is false in the end but you omitted it. From your explanation, it seems the original example is True. I don't really understand the third one though, why is there no reduction of any kind if $X$ is the empty set? $\endgroup$ – Andrew Raleigh Mar 19 at 19:50
  • 1
    $\begingroup$ Yes, I noticed "is false" in the end of your question. I moved it to the front for clarity. A reduction is required to map a yes instance to a yes instance. Let $y$ be a yes instance. Now, how can you map $y$? You cannot. (There is no function from a nonempty domain to an empty codomain). $\endgroup$ – Apass.Jack Mar 19 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.