2 ms·
> Problems can get way, way harder than NP. I don't think anyone doubts that. NP vs P is just talked about because its the dividing line where things first bec
by bawolff 4y ago
> Problems can get way, way harder than NP.
I don't think anyone doubts that. NP vs P is just talked about because its the dividing line where things first become too hard (to overgeneralize). There are lots of NP problems that are close to being tractable so it feels like they are in reach. There are also lots in this category that are things that are useful to do. While there are certainly exceptions, harder categories have problems that seem more obviously out of reach at a glance.
- Sharlin 4y agoIndeed NP problems are in a way astonishingly easy in that they have the very specific, curious property of being polynomial-time verifiable, which is clearly not true for arbitrary hard problems. In other words, problems in NP are those that can be brute-forced because checking an individual answer candidate is cheap. (This is, of course, just another way to phrase the definition of NP: the class of problems solvable in polynomial time on a non-deterministic TM.)