6 ms·
> at least NP hard Excuse me, I have a question. I was under the impression something is either NP hard or it is not. When you say "at least NP hard" it sugg
by htag 3y ago
> at least NP hard
Excuse me, I have a question. I was under the impression something is either NP hard or it is not. When you say "at least NP hard" it suggests there are levels beyond NP. Am I misinformed, or am I misunderstanding you?
- GolDDranks 3y agoNot 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!