3 ms·

A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-har

by saghm 2y ago

A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems. https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness

gpm 2y ago
Not undecidable, it's just not possible to verify if an answer is correct in polynomial time. There are problems know to be decidable, known to be NP-hard and outside of NP. (E.g. in NEXPTIME)
- saghm 2y ago
  Good to know! I guess I didn't recall as well as I thought.