6 ms·

NP is not an abbreviation for "non-polynomial". You made a very good attempt at explaining P vs NP, but just like most of the other articles that try to make it

NP is not an abbreviation for "non-polynomial". You made a very good attempt at explaining P vs NP, but just like most of the other articles that try to make it digestible for a wider audience you screwed up by leaving out the deterministic vs non-deterministic bit. Sorry for putting it so harsh.

gauravk92 14y ago
Can you provide further reading where OP fell short?
- toemetoch 14y ago
  I came across a very good text in 2008 from the time when there was a lot of confusion whether simulated annealing had cracked it. Someone had gone through a lot of trouble to explain p vs np and the position of sim. annealing with respect to complexity theory. Should be on my computer at work (currently on mobile) .
dshipper 14y ago
Hey thanks for the comment! I don't think I ever said that NP was an abbreviation for "non-polynomial" although I guess that could be inferred by a reader since I never explicitly said what it stood for. I did kind of address the deterministic vs non-deterministic aspect of P v NP in the P.S section without explicitly naming the terms I was talking about. I can understand what you're saying and you're right I chose to leave some things out to make it more digestible and because I felt like a rough knowledge of the concepts was enough to understand the larger point.
- toemetoch 14y ago
  I read the abbreviation from both the footnote ("... NP problems i.e. non-polynomial time...") and the text (" Problems in NP are not known to be solvable in polynomial time. " ... actually they're non-deterministic polynomial). Anyway, you're very close. If you find a way to weave in that missing aspect you'll nail the subject.
  - dshipper 14y ago
    Thanks! I removed the part from the footnote, and added " solvable in polynomial time by a deterministic machine." Still thinking about how best to explain determinism vs. non-determinism but perhaps that's best left for another post. Thanks for pointing those things out :)
    - toemetoch 14y ago
      Still thinking about how best to explain determinism vs. non-determinism Yep, that's a tough one. But before you think of how to explain it please consider how you're going to use that knowledge to explain that in a non-deterministic you can solve an NP problem in polynomial time. That's IMO the hard bit.
powera 14y ago
Also, the article's description of the traveling salesman problem is a completely different problem of finding a http://en.wikipedia.org/wiki/Hamiltonian_path http://en.wikipedia.org/wiki/Hamiltonian_path . http://en.wikipedia.org/wiki/Travelling_salesman_problem http://en.wikipedia.org/wiki/Travelling_salesman_problem
- dshipper 14y ago
  You're right about that. The traveling salesman is slightly different than Hamiltonian path because it's looking to find the lowest possible distance, but I thought it worked nicely as a metaphor. I should have said that instead of referring to it as the traveling salesman problem.

gauravk92 14y ago

Can you provide further reading where OP fell short?

toemetoch 14y ago
I came across a very good text in 2008 from the time when there was a lot of confusion whether simulated annealing had cracked it. Someone had gone through a lot of trouble to explain p vs np and the position of sim. annealing with respect to complexity theory. Should be on my computer at work (currently on mobile) .

dshipper 14y ago

Hey thanks for the comment! I don't think I ever said that NP was an abbreviation for "non-polynomial" although I guess that could be inferred by a reader since I never explicitly said what it stood for. I did kind of address the deterministic vs non-deterministic aspect of P v NP in the P.S section without explicitly naming the terms I was talking about. I can understand what you're saying and you're right I chose to leave some things out to make it more digestible and because I felt like a rough knowledge of the concepts was enough to understand the larger point.

toemetoch 14y ago
I read the abbreviation from both the footnote ("... NP problems i.e. non-polynomial time...") and the text (" Problems in NP are not known to be solvable in polynomial time. " ... actually they're non-deterministic polynomial). Anyway, you're very close. If you find a way to weave in that missing aspect you'll nail the subject.
- dshipper 14y ago
  Thanks! I removed the part from the footnote, and added " solvable in polynomial time by a deterministic machine." Still thinking about how best to explain determinism vs. non-determinism but perhaps that's best left for another post. Thanks for pointing those things out :)
  - toemetoch 14y ago
    Still thinking about how best to explain determinism vs. non-determinism Yep, that's a tough one. But before you think of how to explain it please consider how you're going to use that knowledge to explain that in a non-deterministic you can solve an NP problem in polynomial time. That's IMO the hard bit.

powera 14y ago

Also, the article's description of the traveling salesman problem is a completely different problem of finding a http://en.wikipedia.org/wiki/Hamiltonian_path http://en.wikipedia.org/wiki/Hamiltonian_path . http://en.wikipedia.org/wiki/Travelling_salesman_problem http://en.wikipedia.org/wiki/Travelling_salesman_problem

dshipper 14y ago
You're right about that. The traveling salesman is slightly different than Hamiltonian path because it's looking to find the lowest possible distance, but I thought it worked nicely as a metaphor. I should have said that instead of referring to it as the traveling salesman problem.