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.
Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy?
complexity theory;terminology;optimization;integer programming