Success is in NP | Hacker News Reader

Success is in NP

danshipper.com

11 pointsdshipper13 comments

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.

Can you provide further reading where OP fell short?

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) .

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.

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.

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 :)

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.

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/Travelling_salesman_problem

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.

"P problems are in fact contained within the set of NP problems i.e. non-polynomial time solutions exist for P problems. However, all problems in NP may or may not be in P."

Yes, P is in contained in NP. However, the reason is wrong. It is contained in NP because any problem in P is verifiable in polytime (i.e. by actually solving it).

I edited that part out to be safe. But I'm curious. I was trying to explain why P problems were in NP and my off the top of my head reasoning was that deterministic non-polynomial time solutions exist for P problems as well as deterministic polynomial time ones.

If that's not why P is contained in NP, what's the real reason?

Since a problem in P is can be solved in polynomial time, then a solution to it can be verified in polynomial time. If it can be verified in polynomial time, then it is in NP. It's this simple.

However, it has nothing to do with "non-polynomial" time solutions, as you originally stated. NP and non-polynomial doesn't have a correspondence by their definitions.

Got it. Thanks for the clarification.

Reply on news.ycombinator.com