5 ms·

That's not right. The names of the classes can be confusing, but ${CLASS}-hard means "no harder than ${CLASS}", not " no easier than ${CLASS}". So, for instan

That's not right. The names of the classes can be confusing, but ${CLASS}-hard means "no harder than ${CLASS}", not " no easier than ${CLASS}". So, for instance, every problem in P is NP-hard. ${CLASS}-complete, on the other hand, means that its members are both: 1. ${CLASS}-hard and 2. No easier than any other problem in ${CLASS}.

drdeca 10y ago
Oh! Thank you for correcting me on that. I had based my understanding on images like this one, which is in the article: https://cdn-images-2.medium.com/max/1800/1*_iqZ21FEdk-A_A0-jcM-Qg.png https://cdn-images-2.medium.com/max/1800/1*_iqZ21FEdk-A_A0-j... Which I thought said that everything which is at least as complex as everything in NP was in NP hard. Thank you for correcting me on that. Is there a term for "every problem such that being able to solve it in P time would allow you to solve NP problems in P time" (or, whatever is the correct way to phrase that)?
- procrastitron 10y ago
  That statement is true of NP-complete; if you can solve any NP-complete problem in P time, then you can solve every NP-hard problem in P time.
  - drdeca 10y ago
    I thought NP-complete implied that the problem was also in NP, in addition to satisfying that statement. Does it not?
    - danbruc 10y ago
      As Chinjut already pointed out, procrastitron got it wrong. So let's set things straight. 1. A problem is in NP if it is a decision problem and polynomial time verifiable proof exist if the answer is yes. 2. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. 3. A problem is NP-complete if it is NP-hard and in NP. Things to note. NP is about decision problem, problems with a yes or no answer. Finding the shortest travelling salesman tour is not NP-complete, it is not even in NP, because it is not a decision problem. And even ignoring that it is not a decision problem, there is also no polynomial time verifiable proof. You could show me your solution but how would I verify that it is indeed the shortest tour without computing the shortest tour myself and comparing it with your solution? The decision version of the travelling salesman problem - exists a tour with costs less than X - is in NP. It is a decision problem and as proof you can just show me the tour and I can check that it is a valid tour and has costs less than X in polynomial time. Further if there is no tour with costs less than X, then you don't have to be able to proof this to me, only if the answer is yes. How would you proof to me that there is no tour with costs less than X? Decisions problems with proofs if the answer is no are in co-NP. A problem can have proofs in both cases, then it is in the intersection of NP and co-NP. A problem is NP-hard if you can reduce every problem in NP to it in polynomial time, i.e. if you can solve a NP-hard problem, then you can solve all problems in NP with at most a polynomial slowdown. In other words NP-hard problems are at least as hard as the hardest problems in NP. A NP-hard problem is not required to be a decision problem, does not have to have polynomial time verifiable proof, it does not even have to be decidable. Finding the shortest travelling salesman tour is NP-hard and an example of not being a decision problem and not having polynomial time verifiable proof. But if you can find the shortest tour, then you can trivially solve the decision version of the travelling salesman problem which is NP-complete. A problem is NP-complete if it is NP-hard and in NP, i.e. NP-complete problems are the NP-hard decision problems with polynomial time verifiable proof if the answer is yes.
      - drdeca 10y ago
        Thank you very much. This is much closer to what I had thought before I read what procrastitron said (though I was missing a number of the details such as things regarding NP vs co-NP ). Thanks to you and Chinjut for clearing this up. Also, this seems like this means that in my first comment my statement of " if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]." was correct? (judging based on your statement that "A problem is NP-complete if it is NP-hard and in NP", which seems to roughly say what I said in my first comment). Am I correct in thinking that these say basically the same thing?
        danbruc 10y ago
        I would say it is correct, it just seems a somewhat strange scenario to me. You know a problem is NP-hard and it of course has to be a decision problem or it could never end up in NP and then you show that it is indeed in NP, i.e. you show that it also has a polynomial time verifiable proof, which then makes the problem NP-complete. That does not sound impossible but I am not aware or can think of an example where it was hard to figure out that such a polynomial time proof is possible. I would love to know if there are examples but I really don't know.
- acchow 10y ago
  Grandparent post is actually wrong. NP-hard roughly means "no easier than NP". Basically grandparent got it backwards.
  - drdeca 10y ago
    Alright, thanks.
Chinjut 10y ago
Sorry, you are wrong. Your description of ${CLASS}-hard is precisely backwards. For example, see Wikipedia: https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness "NP" itself already means "No harder than NP-complete" [under Karp reduction; Cook reduction perhaps tracks ordinary language "hard" better, but, whatever]. "NP-hard" means "No easier than NP-complete". "NP-complete" means, well, "Exactly as easy as NP-complete" [again, under Karp reduction].
- procrastitron 10y ago
  You are right; I got it backwards.

drdeca 10y ago

Oh! Thank you for correcting me on that. I had based my understanding on images like this one, which is in the article: https://cdn-images-2.medium.com/max/1800/1*_iqZ21FEdk-A_A0-jcM-Qg.png https://cdn-images-2.medium.com/max/1800/1*_iqZ21FEdk-A_A0-j... Which I thought said that everything which is at least as complex as everything in NP was in NP hard. Thank you for correcting me on that. Is there a term for "every problem such that being able to solve it in P time would allow you to solve NP problems in P time" (or, whatever is the correct way to phrase that)?

procrastitron 10y ago
That statement is true of NP-complete; if you can solve any NP-complete problem in P time, then you can solve every NP-hard problem in P time.
- drdeca 10y ago
  I thought NP-complete implied that the problem was also in NP, in addition to satisfying that statement. Does it not?
  - danbruc 10y ago
    As Chinjut already pointed out, procrastitron got it wrong. So let's set things straight. 1. A problem is in NP if it is a decision problem and polynomial time verifiable proof exist if the answer is yes. 2. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. 3. A problem is NP-complete if it is NP-hard and in NP. Things to note. NP is about decision problem, problems with a yes or no answer. Finding the shortest travelling salesman tour is not NP-complete, it is not even in NP, because it is not a decision problem. And even ignoring that it is not a decision problem, there is also no polynomial time verifiable proof. You could show me your solution but how would I verify that it is indeed the shortest tour without computing the shortest tour myself and comparing it with your solution? The decision version of the travelling salesman problem - exists a tour with costs less than X - is in NP. It is a decision problem and as proof you can just show me the tour and I can check that it is a valid tour and has costs less than X in polynomial time. Further if there is no tour with costs less than X, then you don't have to be able to proof this to me, only if the answer is yes. How would you proof to me that there is no tour with costs less than X? Decisions problems with proofs if the answer is no are in co-NP. A problem can have proofs in both cases, then it is in the intersection of NP and co-NP. A problem is NP-hard if you can reduce every problem in NP to it in polynomial time, i.e. if you can solve a NP-hard problem, then you can solve all problems in NP with at most a polynomial slowdown. In other words NP-hard problems are at least as hard as the hardest problems in NP. A NP-hard problem is not required to be a decision problem, does not have to have polynomial time verifiable proof, it does not even have to be decidable. Finding the shortest travelling salesman tour is NP-hard and an example of not being a decision problem and not having polynomial time verifiable proof. But if you can find the shortest tour, then you can trivially solve the decision version of the travelling salesman problem which is NP-complete. A problem is NP-complete if it is NP-hard and in NP, i.e. NP-complete problems are the NP-hard decision problems with polynomial time verifiable proof if the answer is yes.
    - drdeca 10y ago
      Thank you very much. This is much closer to what I had thought before I read what procrastitron said (though I was missing a number of the details such as things regarding NP vs co-NP ). Thanks to you and Chinjut for clearing this up. Also, this seems like this means that in my first comment my statement of " if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]." was correct? (judging based on your statement that "A problem is NP-complete if it is NP-hard and in NP", which seems to roughly say what I said in my first comment). Am I correct in thinking that these say basically the same thing?
      - danbruc 10y ago
        I would say it is correct, it just seems a somewhat strange scenario to me. You know a problem is NP-hard and it of course has to be a decision problem or it could never end up in NP and then you show that it is indeed in NP, i.e. you show that it also has a polynomial time verifiable proof, which then makes the problem NP-complete. That does not sound impossible but I am not aware or can think of an example where it was hard to figure out that such a polynomial time proof is possible. I would love to know if there are examples but I really don't know.
acchow 10y ago
Grandparent post is actually wrong. NP-hard roughly means "no easier than NP". Basically grandparent got it backwards.
- drdeca 10y ago
  Alright, thanks.

Chinjut 10y ago

Sorry, you are wrong. Your description of ${CLASS}-hard is precisely backwards. For example, see Wikipedia: https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness "NP" itself already means "No harder than NP-complete" [under Karp reduction; Cook reduction perhaps tracks ordinary language "hard" better, but, whatever]. "NP-hard" means "No easier than NP-complete". "NP-complete" means, well, "Exactly as easy as NP-complete" [again, under Karp reduction].

procrastitron 10y ago
You are right; I got it backwards.