Before explaining what NP-Completeness actually means, let’s explain the concept of NP-hardness first. NP-hard is the class of problems that are “at least as hard as all the problems in NP”. The NP-complete class, on the other hand, contains the NP-hard problems that are in NP. The following diagram will help you get the picture:
Another aspect worth mentioning is that the NP-Complete complexity class is a class of decision problems. Decision problems are those problems that, given an input, output “yes” or “no”.
Take, for example, Tetris.
Determining whether a player can survive on a Tetris board given a configuration of pieces is a decision problem. There is no efficient way to compute the order of moves the player can make in order to survive, so the task is NP-hard.
However, we could certainly write a program that runs in polynomial time to simulate the way the player has arranged the given pieces and check whether they survived or not. This means Tetris is also in NP because, as mentioned above, for any problem in NP we can write a program in polynomial time to check whether a solution holds or not. But since it is also NP-hard, we can say Tetris is NP-complete.
For example, the classic knapsack problem can be solved in polynomial time with various methods, including a greedy approach or dynamic programming. However, the decision problem form of knapsack (i.e. Can a value V be achieved without going over a given weight W?) appears to be part of the NP-complete class, as there is no algorithm that can solve this problem in polynomial time. The same can be said about graph coloring, for example.