Is there an optimization variant of NP completeness 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  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

*I just found the publicationVerifying Integer Programming Results in which certificates for optimal integer solutions of linear programs are discussed.

 A: 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) 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.
A: So, 3-SAT can be considered an optimization problem. You want to find an assignment of the variables, so that the expression becomes 1. The maximal possible value is 1, minimal possible value is 0, for a 3-sat expression.
Thus, optimization here is same as solving the 3-sat problem.
Now, verification is easy, but finding the variables is hard.
Similarly, there are some optimization problems, where one wants to optimize say $f$, and deciding if $f > M$ for some fixed $M$ is NP-complete. Verifying that $f > M$ is easy, but finding the solution is hard. I have a document on arxiv, where I show that certain variations of maximal flow, and shortest path, have these properties.
A: Integer programming is NP-complete.
