1
$\begingroup$

According to the polynomial-time-reduction definition

"If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq_p X$."

If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

In other words, does lower bounds for $X$ and $Y$ matter?

$\endgroup$

migrated from stackoverflow.com Apr 27 '17 at 4:02

This question came from our site for professional and enthusiast programmers.

4
$\begingroup$

Note that you got it wrong in the question. What you have is that if $Y \leq^p_m X$ and $Y$ is NP-hard, then $X$ is also NP-hard. This is true by definition, unconditional on any other lower bounds known for $X$ or $Y$ (though, as Ryan points out, such lower bounds could be very interesting).

If $X$ is in NP and has a lower bound on its computational complexity that is super-polynomial, it would mean that $P \neq NP$.

$\endgroup$
1
$\begingroup$

When dealing with known NP-complete problems, they will not have a proven lower bound. If they were to have a proven lower bound, then you could conclude some very interesting results about P vs NP. This question explains what conclusions you could possibly make if you proved a non-polynomial lower bound for an NP-complete problem. This explanation goes in depth with why lower bound proofs are so difficult. This isn't much of an answer, more of a point in the right direction.

$\endgroup$
1
$\begingroup$

"If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq_p X$."

If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

No, that's backwards. Very informally, $Y\leq_{\mathrm{p}} X$ means that $Y$ is no harder to solve than $X$.

Still informally, but a bit more precisely, $Y\leq_{\mathrm{p}} X$ means that we can solve $Y$ by doing a little [a polynomial amount of] work and then solving $X$. A problem $L$ being NP-hard means that we can solve every problem in NP by doing a little work and then solving $L$. Finally, $L$ is NP-complete if it's NP-hard and is, itself, in NP.

So, if $Y$ is NP-complete, and $Y\leq_{\mathrm{p}} X$ then we can solve every problem in NP by doing a little work to convert to $Y$, then doing a little more work to convert to $X$, then solving $X$. This allows us to conclude that $X$ is NP-hard. If $X$ is also in NP, then it is NP-complete.

On the other hand, if $X$ is NP-complete and $Y\leq_{\mathrm{P}}X$, all we can conclude is that $Y$ is in NP. Informally, we've been told that $Y$ is no harder than some NP-complete problem. $Y$ could be NP-complete, or it could be really easy, or something between the two.

From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

It's not that "$p$ should always be polynomial": p doesn't denote a function; rather, it stands for the word "polynomial". (If you look carefully, you'll notice that I've typeset it as $\leq_{\mathrm{p}}$, denoting a type of reduction that's called "p", rather than $\leq_p$, which would be a type of reduction parameterized by some mathematical object $p$.)

So your remark is a bit like defining $A\to_{\mathrm{T}}B$ to mean that you can get from city $A$ to city $B$ by train and then saying, "From my understanding, T should always be a train and cannot be another means of transport, such as a car or bus." Well, yes: it's a train because we defined it to be a train. It makes complete sense to ask about cars and buses and functions that aren't polynomials, but "p" means "polynomial" because that's what we decided it would mean.

However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

This is a different question again. The "p" in $\leq_p$ refers to a polynomial amount of work done translating between two problems. That concept is independent of the difficulty of solving the problems themselves. For example, SAT and 3-colourability are both quite difficult to solve (nobody knows an efficient algorithm for either) but it's quite easy to translate between them (we make undergraduates do it as an exercise, and most of them survive).

As it stands, we don't have any super-polynomial lower bounds on the complexity of solving any NP-complete problem on a deterministic Turing machine. That would prove that P$\,\neq\,$NP which would be... quite a big deal.

In other words, does lower bounds for $X$ and $Y$ matter?

NP-hardness is a lower bound: it says that the problem cannot be (much) easier than any problem in NP. More generally, if $Y\leq_{\mathrm{p}}X$ then a lower bound on $Y$ does translate to a lower bound on $X$. This is because the lower bound on $Y$ says "Every possible way of solving $X$ requires at least this much computational resources", and "any possible way" includes "translate to $X$ and then solve $X$."

In general, a lower bound on $X$ doesn't tell you anything. We just know that $Y$ is at most as hard as something which is at least "this hard", but that doesn't say anything, in the same way that "$x<y$ and $y>3$" doesn't restrict the value of $x$ at all.

$\endgroup$

Your Answer

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