Hacker News new | past | comments | ask | show | jobs | submit login

I read that differently. There are harder problems in NP, in the same way there are 7ft tall people in the set of people over 6ft tall. So ‘at least NP hard’ I understood as ‘in NP but maybe in a subset of NP that is harder’.



Oh, so you mean like, supposing that NPI exists, an NPI problem? https://en.wikipedia.org/wiki/NP-intermediate

> There are harder problems in NP

That is an unresolved question. It might turn out that every problem in NP is equally hard. (Up to a polynomial translation cost.)


Thanks for the better information!




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: