0

I'm trying to wrap my head around what all these terms mean and here is my understanding so far. I'm hoping you can improve my understanding of what these terms mean.

P is the set of all problems which can be efficiently solved.

NP is the set of all problems that can be checked for correctness if you guess an answer.

NP-hard is the set of all problems that are at least as hard as the hardest NP problems

NP-complete is the set of all problems are NP-hard problems that are also NP.

Have I covered anything? Are there any important aspects that I still need to know?

Ogen
  • 2,255
  • 8
  • 31
  • 44

2 Answers2

1

NP is the set of all problems that can be checked for correctness quickly (polynomial time). This part is important. Also, NP-complete is the set of problems that, if any of them can be solved efficiently, then any problem in NP can be solved efficiently (and surprisingly, also the other way around).

Irvan
  • 2,208
1

NP-complete $\subseteq$ NP

NP-complete $\subseteq$ NP-hard

Manolito Pérez
  • 1,241