4 ms·

At the risk of misunderstanding...this article seems completely wrong to me. 1. Technical nitpick: NP-Hard problems are not 'mathematically equivalent'. I assu

by darawk 10y ago

At the risk of misunderstanding...this article seems completely wrong to me. 1. Technical nitpick: NP-Hard problems are not 'mathematically equivalent'. I assume the author means to refer to NP-Complete problems here. NP-Hard is a larger complexity class that may include things that are harder than NP and not equivalent at all to the set of NP-Complete problems. 2. The existence of a physical NP-Complete oracle does not imply that P = NP with respect to classical computing. If tomorrow we discover a physical process that solves travelling salesman in linear time, that does not necessarily mean that P = NP, it simply means we now have a physical oracle for solving the problem. This is the same as with traditional quantum computing. We didn't fold BQP into P when we discovered quantum computing.

drdeca 10y ago
Regarding 1: I think they might have meant that if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]. I'm not sure though.
- procrastitron 10y ago
  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.
  - 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.
pron 10y ago
I think you're being unnecessarily pedantic. Yes, the P v. NP question pertains to Turing machines (and equivalent models), but in this case it is clear that there is an implied appeal to Physical + Complexity-Theoretic/Efficient/Extended Church-Turing Thesis. The paper explicitly says it relies on Cobham's thesis, which can be interpreted (if you squint) to encompass both extended interpretations of C-T. You're right with regards to 1, but the actual paper does not make that mistake. Instead, it states correctly that the problem is NP-hard and therefore a feasible solution (i.e. P) would imply P = NP.

by darawk 10y ago

drdeca 10y ago

Regarding 1: I think they might have meant that if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]. I'm not sure though.

procrastitron 10y ago
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.
- 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.

pron 10y ago

I think you're being unnecessarily pedantic. Yes, the P v. NP question pertains to Turing machines (and equivalent models), but in this case it is clear that there is an implied appeal to Physical + Complexity-Theoretic/Efficient/Extended Church-Turing Thesis. The paper explicitly says it relies on Cobham's thesis, which can be interpreted (if you squint) to encompass both extended interpretations of C-T. You're right with regards to 1, but the actual paper does not make that mistake. Instead, it states correctly that the problem is NP-hard and therefore a feasible solution (i.e. P) would imply P = NP.