Easy to optimize but hard to evaluate

Question

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.

Answer 1

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) 52–58.

Yakov Shafransky

Answer 2

Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.

Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.

Task: Maximize the number of edges in an $n$-vertex graph under the constraint that its maximum clique size is at most $k$.

Solution: It is known from extremal graph theory that the optimal graph will be the Turan graph $T(n,k)$ (see here), which can be easily constructed in polynomial time. On the other hand, checking the quality of a given candidate solution (a given graph) involves checking that its maximum clique size is at most $k$, which is NP-hard.

Note: If we only want to check whether the solution is optimal, then it is easy, because the Turan graph is known to be the unique optimum, so it is enough to compare the candidate graph with the Turan graph, which has a simple structure. On the other hand, if we want to evaluate the quality of a candidate solution, as requested in the question, that is, whether it is feasible and how far it is from the optimum, then we have to check whether it satisfies the maximum clique constraint.