5 ms·
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 po
by 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 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.