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$ .