What is NP-Complete?




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.

NP-Completeness As Tetris-HiringLibrary-ComDetermining 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.


Year of 2015 Version of Java HelloWorldHowever, 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.


Answer of the coding ProblemFinally, it has been observed that some instances of known problems that are normally not in NP are part of this complexity class.

Knapsack Problem HiringLibrary-Com

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.

Previous articleNon Deterministic Polynomial Or NP-Completeness Algorithms
Next articleArray Data Structure
Since last 15 years in different geographical locations, Sumit prepared hiring format for several hiring managers/teams to hire the balanced talents and interviewed talents on the various stages of their selection process. He also interviewed by hundreds of companies in different geographical locations.His best conclusion for hiring teams and candidate is to prepare in advance. Here ‘advance’ means keep your interview book ready and continue to update it even you are not going to interview candidates or applying for any job in next six months.