13 ms·
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
by robotresearcher 3y ago
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’.
- GolDDranks 3y agoOh, so you mean like, supposing that NPI exists, an NPI problem? https://en.wikipedia.org/wiki/NP-intermediate 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.)
- robotresearcher 3y agoThanks for the better information!