Theoretical Computer Science
cc.complexity-theory optimization examples
Updated Sat, 11 Jun 2022 10:22:26 GMT

Easy to optimize but hard to evaluate

Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution?

For the sake of concreteness, we may consider polynomial-time solvable optimization problems of the form: "given x, minimize $f(x, y)$", where $f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$ is, say, #P-hard. Such problems clearly exist (for instance, we could have $f(x, 0) = 0$ for all $x$ even if $f$ is uncomputable), but I am looking for ``natural'' problems exhibiting this phenomenon.


In paper [1], there is a problem with the property that finding an optimal element takes polynomial time despite that computing the objective function values is NP-hard (it means that evaluating the quality of a given candidate solution is NP-hard as well).

[1] T.C.E.Cheng, Y.Shafransky, C.T.Ng. An alternative approach for proving the NP-hardness of optimization problems. European Journal of Operational Research 248 (2016) 5258.

Yakov Shafransky

Comments (1)

  • +0 – Sharing some more detail here would be nice. :) — Nov 10, 2015 at 07:00