8
$\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.

$\endgroup$

migrated from cstheory.stackexchange.com Apr 21 '13 at 20:36

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\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 '13 at 20:28
  • $\begingroup$ Note that the statement is not "every IP is NP-hard" but "solving every IP is NP-hard". $\endgroup$ – Raphael Apr 21 '13 at 23:11
  • 1
    $\begingroup$ As an remark, IP for fixed dimension is in P. $\endgroup$ – A.Schulz Apr 22 '13 at 6:51
16
$\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.
$\endgroup$
  • $\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 '13 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 '14 at 15:45
12
$\begingroup$

No, special cases can be easier.

Consider this IP, for example:

$\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$ which is clearly polynomial.

$\endgroup$
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.

$\endgroup$
  • 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 '13 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.

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • 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 '18 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 '18 at 9:30

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.