<p>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).</p>

<p>[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.</p>

<p>Yakov Shafransky</p>

CC BY-SA 3.0
2015-11-10T07:00:35.227Z
Sharing some more detail here would be nice.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-10T06:50:40.030Z
2015-11-10T06:50:40.030Z
Yakov Shafransky
<p>Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is <strong>NP</strong>-hard.</p>

<p><strong>Input:</strong> Positive integers $n,k$ (in unary encoding), with $k\leq n$.</p>

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

<p><strong>Solution:</strong> It is known from extremal graph theory that the optimal graph will be  the Turan graph $T(n,k)$ (see <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n_graph">here</a>), 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 <strong>NP</strong>-hard.</p>

<p><strong>Note:</strong> If we only want to check whether the solution is <em>optimal</em>, 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 <em>quality</em> 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.  </p>

CC BY-SA 3.0
2015-11-05T15:12:24.230Z
2015-11-05T16:14:20.990Z
2015-11-05T16:14:20.990Z
Andras Farago
<p>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?</p>

<p>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.</p>

<cc.complexity-theory><optimization><examples>
Easy to optimize but hard to evaluate
david
# Easy to optimize but hard to evaluate

(Asked by: username_0 on 2015-11-05)

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.

**Tags:** cc.complexity-theory, optimization, examples


---

## 2 answers

### Answer by username_1 on 2015-11-10. Score: 3 | Accepted answer

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.

username_1

> **Comments:**
> **username_2**: Sharing some more detail here would be nice.  :)  

---

### Answer by username_3 on 2015-11-05. Score: 16

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](https://en.wikipedia.org/wiki/Tur%C3%A1n_graph)), 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.


---

