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.

## Solution

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