2
$\begingroup$

I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. This implies in particular that it is not hard for the second level of the polynomial time hierarchy, e.g. for $\Sigma_2^P$ or $\Pi_2^P$. But since optimization problems are only NP-hard, I have no such knowledge. Or are optimization problems usually also $\Sigma_2^P$-hard or $\Pi_2^P$-hard, or just some of them?

Are there any interesting problems from combinatorial optimization that are harder than $\mathcal{NP}$-hard, e.g. hard for the second level of the polynomial time hierarchy?

I am in particular interested in problems from combinatorial optimization, e.g. BP (bin packing), TSP and CVRP (capacitated vehicle routing problem). They are all classified as $\mathcal{NP}$-hard, but CVRP is a generalization of both TSP and BP, so it should be harder? Bin packing should be easier, are there any results showing this? Does anyone know, if there are hardness results for any of these problems that imply more difficult than $\mathcal{NP}$-hard?

I know there are many versions of CVRP and TSP and unfortunately I know not a lot about them.

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ Optimization problems are not decision problems, thus cannot belong to a decision class such as $\mathcal{NP}$. Therefore, they can only be $\mathcal{NP}$-hard and not $\mathcal{NP}$-complete. $\endgroup$
    – Bruno
    Commented Mar 21, 2013 at 10:13
  • 1
    $\begingroup$ This is probably covered by this and this question. $\endgroup$
    – Raphael
    Commented Apr 3, 2013 at 20:26
  • $\begingroup$ @Bruno The interesting question then is, why can they be part of NP-hard, which is also defined as class of decision problems? $\endgroup$
    – Raphael
    Commented Apr 4, 2013 at 6:34

0

Reset to default