According to the selected answer on this question NP-hard problems do NOT have to be decision problem. But by definition all NP-hard problems can be karp-reduced from any NP-problem in polynomial time; thus, implying that the answer from the reduction must be the same as the NP-problem which is yes/no => decision problem. So isn't NP-hard problems in fact always decision problems?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ This seems to be covered by cs.stackexchange.com/q/11009/755, cs.stackexchange.com/q/67300/755, cs.stackexchange.com/q/84076/755, and the Wikipedia article on NP-hardness ("NP-hard: Class of decision problems which are..."). In the future I encourage you to do more research to check whether the question is already answered on this site or in standard resources. $\endgroup$– D.W. ♦Commented Dec 16, 2017 at 17:46
-
$\begingroup$ @D.W. Well in the link I gave in my question there was an answer to a question with over 1k upvotes that said explicitly "NP-hard problems do not have to be in NP, and they do not have to be decision problems." $\endgroup$– FerusCommented Dec 16, 2017 at 17:50
-
$\begingroup$ As Yuval Filmus wrote, Stack Overflow is a site for programmers. In any case I think your question is basically the same as cs.stackexchange.com/q/67300/755 ("How can the "non-decision problem" version be NP-hard? Doesn't this class contain decision problems, by definition? "), and the question is answered there ("When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard."). $\endgroup$– D.W. ♦Commented Dec 16, 2017 at 19:22
-
$\begingroup$ @D.W. Yes, thanks. I got the answer I was looking for. But computer science is the theoretical background for programming so I don't understand your point there. And it doesn't explain why they would say things that would be incorrect. Well anyway, they did this time I suppose, and that's why I asked the question here, which is what I was trying to clarify. $\endgroup$– FerusCommented Dec 16, 2017 at 19:30
-
$\begingroup$ @I wish this wouldn't have been closed. It is the most direct and Googleable version of the question. $\endgroup$– Ciro Santilli OurBigBook.comCommented Jul 9, 2020 at 8:00
Add a comment
|