NP-complete problem whose corresponding optimization problem is not NP-hard

Question

For this question I will refer to$\ NP-hard$ problems as those that are at least as hard as$ \ NP-complete$ problems. That is, a problem$ \ H$ is$\ NP-hard$ if there is an$ \ NP-complete$ problem$\ G$, such that$\ G$ is reducible to$\ H$ in polynomial time.$\ NP-hard$ problems are not restricted to decision problems and are not necessarily in$\ NP$.

Considering the above, is there any optimization problem$\ L$ such that$ \ L \notin NP-hard $ and whose corresponding decision problem is$ \ NP-complete$?

For example, consider the case for the travelling salesman problem. (TSP)

Optimization problem: Given a list of cities and the distances between each pair, what is the shortest path that visits each city and returns to the original city?

Decision problem: Given a list of cities, the distances between each pair and a length$ \ L$, does there exist a path that visits each city and returns to the original city of length at most$\ L$.

It is well known that the decision problem of TSP is$ \ NP-complete$ and its corresponding optimization problem is$\ NP-hard$.

To sum up, what is an example of a$\ NP-complete$ problem whose corresponding optimization problem lies outside the class$\ NP-hard$? Perhaps, it is$\ EXPTIME$.

Answer 1

Take a look at Bellare and Goldwasser, "The complexity of decision vs. search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119. It discusses the issue at length. Perhaps a bit more readable is the class note by Bellare, "Decision versus search".

Answer 2

Not if the objective function is computable in polynomial time. Suppose the optimization problem, $H$, is to find $x$ that maximizes $\Phi(x)$, where $\Phi$ is some computable function (one could take this as the definition of an optimization problem, in which case all optimization problems can be put into this form). The corresponding decision problem is, given $t$, test whether there exists $x$ such that $\Phi(x) \ge t$. Call this decision problem $G$. Suppose $G$ is NP-complete, and moreover suppose that $\Phi$ can be computed in polynomial time. Then $G$ is reducible to $H$ in polynomial time (to solve $G$, solve $H$ to find the optimal $x$, then test whether $\Phi(x) \ge t$). It follows that if the associated decision problem $G$ is NP-complete and if $\Phi$ can be computed in polynomial time, then the optimization problem $H$ is NP-hard.