# NP-Complete problem whose corresponding optimization problem is not NP-Hard

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

Posted on Categories proxies