logoalt Hacker News

xlii • today at 2:04 PM • 1 reply • view on HN

And yet the same explanation is used as computer science courses in universities. Simplifications have their limits. In short P and NP boils to polynomial and non-polynomial solution space.

And yet you haven't pointed it out. I'd recommend reading this blog post that mentions the limits and consequences of simplifications: https://nedbatchelder.com/blog/201711/toxic_experts


Replies

mockerell • today at 2:48 PM

Yeah no. No proper CS course claims that NP is defined to be “hard” problems (whatever you plugin for “hard”). NP is defined in a way where computation models EXIST (be it non deterministic Turing machine or witnesses).

The connection to solution space is also iffy and usually not how people introduce or primarily think of NP.

All your claimed definitons imply that NP and P are disjoint which clearly isn’t the case. I would be more careful