I'm confused with polynomial-time reduction and NP-hardness.

Let's say that the following integer programming is NP-hard.

$\min_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$.

But it is a special case of the following linear programming.

$\min_{x \in X} f(x)$, where $X$ is a compact subset of $\mathbb{R}$.

Then there is a polynomial-time reduction from IP to a special case of LP, where the solution space is restricted to integer points in $X$. Then LP is NP-hard, which is wrong.

What is wrong with this logic, especially with the reduction part?


To be precise, a polynomial-time algorithm for a linear program requires $X$ to be some convex set in $\mathbb{R}$ (not simply a subset of $\mathbb{R}$). Since $K \subset \mathbb{N}$ is not a convex set, an algorithm for linear program might not work for an integer linear program.

To see why decreasing the domian of the input space might not always simplify things; consider the following simple problem:

P1: Given a set $S$ of $n$ positive integers, find an integer in $S$ with minimum value.

P2: Given a set $S$ of $n$ positive integers, find an integer in $S \cup \{0\}$ with minimum value.

To solve P1, the algorithm needs to go through every element of $S$ (in worst case). Therefore, its time complexity is $\Theta(n)$.

To solve P2, the algorithm can simply output $0$ without doing any operation.

  • $\begingroup$ Thank you for your answer. Let me ask a bit more. I thought that reduction is only about the problems and independent from algorithms. In this case, we know that there exists an polynomial time algorithm for LP, but in general, we don't know it. (That's why we try to prove NP-hardness.) Are there any rules of transforming the problems in reduction? I think decreasing the domain happens sometimes in reduction. For example, fixing the value of some variables reduces the dimension of the solution space. What is allowed in reduction and what is not?? $\endgroup$
    – nemy
    Dec 23 '21 at 22:56
  • $\begingroup$ @nemy Yes, you are all correct. For linear programming, if you consider $X$ as any subset of $\mathbb{R}$, then it is indeed $\mathsf{NP}$-hard. However, when $X$ is some convex set in $\mathbb{R}$ then this problem is what we generally call a linear program and there are polynomial-time algorithms for it. $\endgroup$ Dec 24 '21 at 5:50
  • 1
    $\begingroup$ Oh, I see. I broke the convex constraint of LP in reduction. Thanks! $\endgroup$
    – nemy
    Dec 24 '21 at 8:10

There are many problems in your post.

One error in your reasoning is where you say "Then LP is NP-hard". That doesn't follow from your prior statements. The complexity of "LP restricted to integer points" is different from the complexity of "LP".

In addition, you are wrong to call the second program "linear programming". It would only be linear programming if $f$ is linear and $X$ is defined by linear inequalities (i.e., it is a convex polytope).

The "problem" $\min_{x \in X} f(x)$, where $X$ is a compact subset of $\mathbb{R}$, is not even a well-defined algorithmic problem, because you haven't described how $f$ and $X$ are represented. That must be described, as it affects the problem statement itself. Not all $f,X$ can be represented in finite space, so any finite representation inevitably limits the set of $f,X$ that can occur, which in turn changes the problem itself. Similar comments apply to your first problem as well (how is $f$ represented? not all $f$ can be represented in finite space).

Finally, linear programming and integer programming relate to problems over $\mathbb{R}^n$, not $\mathbb{R}$.

  • $\begingroup$ I think, in the question, the definition of LP is misleading. An LP is defined using linear constraints. Therefore, $X$ can not be just any subset of $\mathbb{R}$. It has to be a convex set. Therefore, R.H.S. is not actually an LP. $\endgroup$ Dec 24 '21 at 6:08
  • $\begingroup$ @InuyashaYagami, good point! I've added to my answer some other issues in the post. $\endgroup$
    – D.W.
    Dec 24 '21 at 17:55
  • $\begingroup$ Hi D.W., thanks for pointing out the issues. But I am not convinced with your first statement. If suppose there exists a polytime reduction from Integer linear program (IP) to linear program (LP), then it does imply that LP is NP-hard since IP is known to be NP-hard. What I am missing? $\endgroup$ Dec 24 '21 at 19:05
  • 1
    $\begingroup$ @InuyashaYagami, sure, yes, your statement is true in isolation, but the statement in the post is not accurate; the post does not show a reduction to LP, it shows a reduction to some other problem, then assumes/pretends/conflates that problem with LP. In other words, the logic of the post is "here is a reduction from IP to Q, therefore LP is NP-hard" -- I am pointing out that Q is different from LP, so that statement doesn't follow. Logic like "here is a reduction from IP to LP, therefore LP is NP-hard" would be correct, but the post doesn't show a reduction from IP to LP. $\endgroup$
    – D.W.
    Dec 24 '21 at 19:07
  • $\begingroup$ Agreed. Thanks! $\endgroup$ Dec 24 '21 at 19:09

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.