7
$\begingroup$

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.
Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Linear programming used to be like that, since the coincidence of the primal and dual feasible values proves optimality. But then someone proved it is polynomial time. $\endgroup$
    – Brendan McKay
    Commented Jul 22, 2022 at 6:48
  • 1
    $\begingroup$ This is for more general search problems rather than just optimization problems, but see en.wikipedia.org/wiki/TFNP . $\endgroup$
    – Emil Jeřábek
    Commented Jul 22, 2022 at 9:36
  • 3
    $\begingroup$ In graph problems there are obstructions called "viruses". If you have found expected optimal 4 coloring of graph, it will be really optimal if the graph contains induced K_4, which is a certificate that 3 coloring doesn't exist. $\endgroup$
    – joro
    Commented Jul 22, 2022 at 10:47
  • 1
    $\begingroup$ @PerAlexandersson can you explain what is unclear? The question seems well-defined to me. $\endgroup$
    – usul
    Commented Jul 22, 2022 at 17:49
  • 1
    $\begingroup$ I agree with usul that the question is clear. However, the title asks about "completeness" but the question is the body of the post does not really address this aspect. $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2022 at 19:06

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting answer, but how does this jive with Brendan McKay's suggestion that in the (in my opinion conceivable) world where no efficient algorithm for linear programming was known, it would give a good answer. $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2022 at 21:58
  • 1
    $\begingroup$ Linear programming isn't $\mathsf{DP}$-complete, so there's no contradiction. You could scan down the list of potentially $\mathsf{NP}$-intermediate problems to look for candidates, but I don't think any of them fit the bill either. Even if you did find one, it probably wouldn't constitute a "class" of optimization problems, which is what the OP asked for. $\endgroup$
    – Timothy Chow
    Commented Jul 22, 2022 at 22:03
  • $\begingroup$ Well, now that you mentioned NP intermediate, doesn't factoring give a kind of example? Problem Input: a positive integer $n$. Problem Output: expression $n = a_1 \cdots a_k$ for integers $a_i > 1$ of the longest length $k$. Since "PRIME is in P" we can verify a maximal factorization quickly, I think... $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2022 at 22:07
  • 2
    $\begingroup$ @SamHopkins Technically, perhaps, but factorization is not usually considered to be an "optimization" problem, even though you can force it to be one if you insist. $\endgroup$
    – Timothy Chow
    Commented Jul 22, 2022 at 22:09
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How do you verify the optimality of instances with value 0? That's not easy at all, it's coNP-complete. $\endgroup$
    – Emil Jeřábek
    Commented Jul 23, 2022 at 6:32
  • $\begingroup$ @EmilJeřábek Ah, yes, that is correct. $\endgroup$
    – Per Alexandersson
    Commented Jul 23, 2022 at 6:47
0
$\begingroup$

Integer programming is NP-complete.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This could possibly be an answer, but: how do you certify optimality to an integer programming solution? $\endgroup$
    – Sam Hopkins
    Commented Jul 22, 2022 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .