3 ms·
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
by 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 agoI 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 agoThanks! 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 agoStill 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.