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

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.

---

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:/

---

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.

---

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.