3 ms·

Can you explain your usage of NP hard in your comment?

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