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.

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

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.