1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How can$ \ G$ be NP-complete if $\Phi$ is computable in polynomial time? Would it be because to find the optimal$ \ x$, I would need to test an exponential number of possible values for the function, each of which would take polynomial time? $\endgroup$ – JhonRayo99 Feb 15 at 14:19
  • $\begingroup$ @JhonRayo99, one computation of $\Phi(x)$ takes polinomial time (polinomial in the size $\lvert x \rvert$), if you need to run it on an exponential number of candidate $x$, time will be more than exponential. $\endgroup$ – vonbrand Feb 16 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.