logoalt Hacker News

mockerell • today at 2:48 PM • 0 replies • view on HN

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