Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Fwiw, NP includes P, so it's not true that problems in NP are hard to solve, easy to verify. You want to limit the statement to NP-complete problems. Even then, it's only true that solving the problems in full generality is (conjectured) hard. Individual instances can be easy, and in some applications, it may be the case that all/most problems that occur in practice are easy. Even SAT can be easy in practice, and modern SAT solvers solve instances with millions of variables every day.



Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: