14
$\begingroup$

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming problem, but the Wikipedia page states that this is NP-Hard. To me, this implies the assignment problem is in NP-Hard.

But surely the assignment problem can't be in both P and NP-Hard, otherwise P would equal NP? Does the Wikipedia page simply mean that the general algorithm for solving all ILP problems is NP-Hard? A few other sources state that ILP is NP-Hard so this is really confusing my understanding of complexity classes in general.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ NP-hard means that (unless P = NP) every polytime deterministic algorithm fails on some (infinite) set of instances. There usually are sets of easy instances as well. $\endgroup$
    – Sasho Nikolov
    Apr 21, 2013 at 20:28
  • 1
    $\begingroup$ Note that the statement is not "every IP is NP-hard" but "solving every IP is NP-hard". $\endgroup$
    – Raphael ♦
    Apr 21, 2013 at 23:11
  • 1
    $\begingroup$ As an remark, IP for fixed dimension is in P. $\endgroup$
    – A.Schulz
    Apr 22, 2013 at 6:51

5 Answers 5

Reset to default
22
$\begingroup$

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second. A method of proving the hardness of a decision problem $P$ is devising a polynomial (Karp) reduction from another problem $Q$ that is known to be NP-Hard. In this reduction you show that there exists a function $f$ that maps each instance $q$ of the problem $Q$ to an instance of the problem $P$ such that: $q$ is a yes instance for $Q \iff f(q)$ is a yes instance for $P$. This implies that solving $f(q)$ must be "at least as difficult" as solving $q$ itself.

Notice how it's not required for the image of $f$ to be equal to the set of the instances of $P$ . Therefore it's perfectly possibile for problem $P$ restricted to some subset of instances to not be hard.

To return to your original question:

  • The assignment problem can be solved in polynomial time, i.e., a solution to each instance of the assignment problem can be computed in polynomial time.
  • ILP is NP-Hard: in general it might be hard to compute a solution to an ILP problem, i.e. there are instances of ILP that are hard.
  • Some specific instances of ILP can be solved in polynomial time.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you please explain is it necessary for $f$ to map each instance of $Q$ cannot we map a subset of $Q$ ? i.e. does pre-image of $f$ has to be be all of $Q$? $\endgroup$
    – Mat
    Dec 24, 2013 at 3:02
  • $\begingroup$ It is not necessary for $f$ to map each instance of $Q$ as long as it maps an (infinite) class of hard instances of $Q$. For example, in order to show that $P$ is NP-Hard, one can provide a reduction from the 3-coloration problem restricted to planar graphs. $\endgroup$
    – Steven
    Mar 9, 2014 at 15:45
14
$\begingroup$

No, special cases can be easier.

Consider this IP, for example, given $a_i \geq 0$ for $i \in [1..n]$:

$\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$

s.t. $\quad\displaystyle\sum_{i=1}^n x_i \geq 1$
and $\ \displaystyle x_i \in \mathbb{N}$ for $i \in [1..n]$.

It finds the minimum among $a_1, \dots, a_n$ (that for which, inevitably, $x_i=1$ in an optimal solution). Finding the minium of $n$ numbers is clearly a polynomial problem.

Improve this answer
$\endgroup$
0
0
$\begingroup$

You can model a polynomially solvable problem as an IP. This does not mean the problem is NP-hard. It simply means that there is no known polynomial algorithm for solving the IP model of your problem (unless P=NP).

So as you suggested, the assignment problem is in P but your IP model of it is NP-hard.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The IP in Raphael's answer can be solved in polynomial time. In other words, in general we don't know of a fast algorithm for solving IPs, but there are special cases of IP problems for which we do have fast algorithms. $\endgroup$
    – Juho
    Jul 22, 2013 at 11:43
0
$\begingroup$

No, there are a special kind of integer program, if the constraint matrix is TUM (totally unimodular matrix), then it can be relaxed into the linear program, which can be solved in polynomial time.

Improve this answer
$\endgroup$
-4
$\begingroup$

The assignment problem is not a ILP, but an LP problem and therefore not NP-hard.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ I'm not sure why you think that the assignment problem is not an ILP. It so happens that, in this case, the optimal solution to the linear program is also the optimal solution to the integer linear program... but that doesn't mean it's not an instance of ILP. $\endgroup$
    – D.W. ♦
    Mar 21, 2018 at 16:06
  • $\begingroup$ Also, individual instances by themselves are never NP-hard. You want to say "this is actually an easy instance", but that's a much more complicated statement (define "easy"). $\endgroup$
    – Raphael ♦
    Mar 22, 2018 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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