4 ms·
No, you know if you're getting better or worse in an NP problem because checking answers is in P.
by whatshisface 5y ago
No, 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.)