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

> 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?



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".


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!


I 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




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

Search: