**Question:**  

is there a class of optimization problems for whose solution no efficent algorithm is known, but for which the claimed optimality of a solution can efficiently be verified?


**Edits:**


* There is the publication [Optimality conditions and complete description of polytopes in combinatorial optimization](https://arxiv.org/abs/1809.04363) with optimality criteria for combinatorial optimization problems; the question would be if any of those criteria allow for an efficient evaluation.  

-The requested clarification of the is simple: if e.g. the underlying toplogical graph contains multiple \*yes" instances, the question is as to whether it can efficiently be decided whether a specific such instance also is the one with optimal sum of edge weights.
* Ground states of 3D spin glasses are apparently a combinatorial optimization problem for which the optimal *value* can be calculated without actually determining the solution, so it can efficiently be checked whether a "yes" instance of the underlying decision problem also has optimal edge weight sum. cf [Checking for optimal solutions in some NP-complete problems](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjBlO2Iio35AhWSiP0HHTKlBScQFnoECAIQAQ&url=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F7568085_Checking_for_Optimal_Solutions_in_Some_NP-Complete_Problems&usg=AOvVaw2UlWygGHGH1qmjfgQKvX19)
* I just found the publication[Verifying Integer Programming Results](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj52J7Tgqv5AhVRgv0HHYHsCtIQFnoECAMQAQ&url=https%3A%2F%2Fopus4.kobv.de%2Fopus4-zib%2Ffiles%2F6104%2FZR-16-58.pdf&usg=AOvVaw2ytzHfdswej5kwigNtPfY9) in which certificates for optimal integer solutions of linear programs are discussed.



Is there an optimization variant of NP completeness
It is unlikely that there is an interesting class of such optimization problems, for the following reason.


Following Chapter 17 of Papadimitriou's book *Computational Complexity*, let EXACT TSP denote the following problem: Given a distance matrix and an integer $B$, is the length of the shortest tour *equal to* $B$? Then Theorem 17.2 of Papadimitriou states that EXACT TSP is $\mathsf{DP}$-complete, where a language $L$ is in the class $\mathsf{DP}$ ([difference polynomial time](https://complexityzoo.net/Complexity_Zoo:D#dp)) if there exists a language $L\_1 \in \mathsf{NP}$ and a language $L\_2 \in \mathsf{coNP}$ such that $L = L\_1 \cap L\_2$. (Note that $\mathsf{DP}$ is *not* the same as $\mathsf{NP}\cap \mathsf{coNP}$.) Papadimitriou goes on to say that most other naturally occurring exact-cost optimization problems are also $\mathsf{DP}$-complete.


If it were easy to verify the optimality of an allegedly optimal solution to TSP, then EXACT TSP would be in $\mathsf{NP}$ (the optimal solution would be a short certificate). In particular, this would imply $\mathsf{DP} \subseteq \mathsf{NP}$. However, $\mathsf{DP} \subseteq \mathsf{NP}$ is certainly not known, and is probably not even true. More generally, no $\mathsf{DP}$-complete problem is going to be an example of what you're looking for, and that rules out a large number of candidates.


