4 ms·
I wouldn’t be surprised to learn that even being less wrong is NP-hard.
by hanche 5y ago
I wouldn’t be surprised to learn that even being less wrong is NP-hard.
- whatshisface 5y agoThe saving grace of being able to survive in the universe is that it's possible to climb up NP hard problems far enough to get real results with hard work.
- hanche 5y agoIndeed. And thanks! I needed a little morale booster now, for reasons unrelated to this topic.
- mensetmanusman 5y agoIt also means that you might not know if the hard work is climbing up or down (towards or away) from the solution.
- whatshisface 5y agoNo, you know if you're getting better or worse in an NP problem because checking answers is in P.
- mensetmanusman 5y agoIf you find a solution, yes
- whatshisface 5y agoOh, you're thinking of NP-hard yes-no problems. Many if not most NP-hard problems of practical importance, including the traveling salesman, involve integer rather than boolean scores.
- mensetmanusman 5y agoThanks for the additional clarification :)
- karpierz 5y agoNP-hardness by definition is only yes-no decision problems. The NP-hard formulation of Traveling Salesman is "given the weighted graph G and an integer X, is there a Hamiltonian cycle in G with total weight less than X?"
- btilly 5y agoYou are using a non-standard definition of NP-hard. Here are standard definitions. A problem is in P if there is a polynomial time algorithm to solve it. A problem is in NP if there is a polynomial time algorithm to check a purported solution. A problem is in NP-hard if, if there was a polynomial time algorithm to solve it, every problem in NP could be solved in polynomial time. A problem is NP-complete if it is both in NP and in NP-hard. For Traveling Salesman, the NP-complete problem is, "...find a solution with total weight less than X." (Linear verification, check it is Hamiltonian, check its weight.) An NP-hard version is, "...find whether there is a solution with total weight less than X." (To verify, you have to search. Oops.) But ANOTHER NP-hard version is, "...find the solution with least total weight". (To verify, you have to search. Oops.)