The complexity of verifying solutions to NP-hard optimization problems?

Question

There are many optimization problems that are known to be NP-hard, such as the traveling salesman problem, MAX-SAT, or finding the minimum chromatic number of a graph. Given a problem of this sort, I'm curious about the complexity of the following problem:

Given an NP-hard optimization problem and a candidate solution S, is S the optimal solution to the problem?

Intuitively, it seems like this might be co-NP hard, since it's easy to refute an answer to an optimization problem by guessing a better solution and using it as a witness, but I have no idea how to show this. In fact, I don't really know how to reason about the complexity of this problem.

Does anyone know of any good lower bounds on the complexity of this decision problem? Knowing whether this was co-NP hard, PSPACE-hard, etc. would be really interesting.

Machinegun

Assuming that the decision variant of the optimization problem is NP-complete, you've outlined a proof that verifying optimal solutions is in coNP. The most direct route to a hardness result would be a polynomial-time many-one reduction from a coNP-hard problem, but such a reduction would have a difficult time finding a solution to verify. I've taken a graduate-level complexity course and think that this is appropriate for cstheory. – Alanealanine

If the Optimization was an positive integer minimization problem (i.e. the answer is always a positive integer), you could do a binary search using the "IsOptimal" verifier, and so it seems like that would be NP-Hard too... – Faucher

@Moron: Is this necessarily the case? Note that the problem requires an actual candidate solution, not merely its "value". – Exarchate

@mhum: I was talking about the case the value is the solution (like chromatic number). Of course you are right that, if you need a colouring this won't work. – Faucher

@Moron: Indeed, I was interpreting the question as saying a "solution" to, say, chromatic number referred to an actual coloring and not merely the chromatic number itself. I came to this interpretation from the part where the asker uses a guessed solution to deduce that this problem is in co-NP. – Exarchate

Answer 1

The term 'NP-hard optimization problem' seems a bit too broad to let a satisfying answer be found.

For instance, I can't see what precludes decision problems from being considered NP-hard optimization problems - if you consider, say, the MAX-CNF-SAT problem with the solutions being scored as floor(k/N), where k is the number of satisfied clauses and N is the total number of clauses in the instance (which is clearly computable in polynomial time), then any valuation which yields a 1 in this formula will have to satisfy the whole formula. So let's assume that we are maximizing floor(k/N) and call this the FLOOR-CNF-SAT optimization problem:)

This implies you can reduce TAUTOLOGY to said optimization problem - negate the input and add any solution as S. You can even add a dummy variable to make sure the initial solution is gets a 0 in the FLOOR-CNF-SAT problem. Negation is polynomial in time.

Then if a solver for the proposed problem deems S to not be optimal, there must clearly be a valuation which yields a 1 according to our crafted function and thus satisfies the whole formula - in turn providing a valuation that does not satisfy the original input to TAUTOLOGY.

By cheating slightly (using an artificially crafted optimization problem) we have established the 'is optimal' problem as co-NP-complete, since TAUTOLOGY is easily shown to be co-NP-complete.

By your own argument the 'is optimal' decision problem is co-NP-hard, since as a witness you only need a better solution - score S, score the witness and compare.

I don't really feel great about this reduction but I can't easily improve on the problem class. If you require that there be instances which score arbitrarily high and not just {0, 1}, I could just use N * floor(k/N). An improvement to the class could be to only consider a problem an NP-hard optimization problem if for each K there exists an instance that has at least K solutions which all score differently.

I think I can still cheat my way through that:

Consider a reduction that adds N dummy variables to the TAUTOLOGY input as follows:

d1 && d2 && d3 ... && dN && (S)

where S is the negated input. As an initial valuation I choose d1, ..., dN = false, but as a score I give a function that returns 2N - 1 if the first N clauses are all false, otherwise it returns the number of satisfied clauses. Such a function would only return 2N if all the clauses were satisfied but could easily have at least N distinct values.

I am afraid that without some complicated regularity conditions on the scoring function this is the best we can get, unless you consider the definition of an NP-hard optimization problem to be 'a problem for which, given a candidate solution S, we can in polynomial time verify whether S is optimal', in which case 'is-optimal' is clearly P and it's no fun at all:/

Deserted

Answer 2

NP-hard problem is "at least as hard as the hardest problems in NP".

Example of NP-hard problem: halting problem (whether program A can stop or not?) :)

Let's say you have a candidate solution: "no, program A can't stop". We know, that you can't verify it -- it's undecidable.

You can't even check if "yes, program A stops" -- because it may take forever, so it's also undecidable.

Bellda

The halting problem is not NP-hard. It is undecidable (in general). But how do you verify that a route for a traveling salesman is minimum length? It's supposed to be verifiable in polynomial time. – Pyuria

I know, that halting problem is undecidable. I thought, that that there is inclusion - my mistake. – Bellda

But if it comes about TSP. It is supposed to be verifiable in polynomial time, but only TSP's decision version: "is there any better solution than N", where N is some number. – Bellda

Correct me if I'm wrong, but I was under the impression that the halting problem is NP hard in that any problem in NP can be reduced to it in polynomial time. You don't have to be in NP to be NP hard. Am I mistaken about this? – Machinegun

Yes, you dont have to be in NP to be NP-hard. And halting problem is not NP-hard as I wrote before. – Bellda

And to be clear, problem which is in NP and NP-hard is NP-complete. – Bellda

Uh, the halting problem is both undecidable and NP-hard. It's not as if they're mutually exclusive. – Alanealanine

So with regards to this answer, saying that in the worst case this is undecidable doesn't say much. It could still be true that it's co-NP complete, for example. – Machinegun

It should be obvious that halting is NP-hard: Given any problem in NP, I write a program that systematicaly tries all possible proofs until it finds one that proves that the answer is YES. Then I use a solution to the halting problem to decide whether this program halts, which in turn proves whether the answer is YES (if the program halts) or NO (if the program never halts). Being undecidable doesn't make it NP-hard. Being capable of solving any problem in NP (and many other problems) makes it NP-hard. – Bifid

No, halting problem is NP-Hard in the sense that is more difficult than any other problem in NP (by definition). But the statement "being capable of solving any problem in NP makes it NP-hard" is false. No solution exist for the halting problem, is not difficult to find it, it does not and cannot exist! And its proof is logical. So by definition is NP-hard but is not NP, so it is not NP-complete. It's undecidable. – Emersed

Answer 3

Because S is a candidate solution; given that there are no other S in which S can be proven to be greedy or less optimal than any other S. It must be that S is at current the MOST optimal solution for the problem.

Pebrook