4 ms·
Not the parent, but you are correct in that NP-Hard includes also harder problems than the problems in NP. "At least NP-hard" is just "NP-hard".
by GolDDranks 3y ago
Not the parent, but you are correct in that NP-Hard includes also harder problems than the problems in NP. "At least NP-hard" is just "NP-hard".
- jimsimmons 3y agoI meant to say that it being NP hard was the beginning of issues. Even if there was a polynomial time algorithm for it there are other can of worms to deal with. But I was wrong ultimately
- robotresearcher 3y agoI 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!