# NP-Complete and NP-Hard

In this chapter we further the discussion on complexity theory with NP-complete and NP-hard complexity classes.

## We'll cover the following

## NP Complete

Without getting into the mathematical details and jargon, we'll stick to informally defining the complexity class NP-complete. Problems in the NP-complete class are **those problems in NP that are as hard as any other problems in NP**. This may sound confusing but, before we get a chance to define

*NP-hard*problems, one can safely assume that NP-complete problems are the hardest problems to solve in the complexity class NP.

By definition of NP, solutions for NP-complete problems can be verified in polynomial time. The wonderful property about problems in NP-complete class is that if we find a polynomial solution for any one of them, we will have found a solution for all of the NP-complete problems - thus implying P=NP. Take a minute to think through what we just stated. It is a very powerful assertion, claiming that the solution for one problem can unlock solutions to all other problems in NP-complete!

Conversely, if we can prove that no polynomial solution exists for any one of the problems in NP-complete complexity class, then we can say that no polynomial time solution exists for all of the problems in NP-complete - thus implying P≠NP.

NP-complete problems exhibit two properties:

- They are in NP, i.e. given a solution one can quickly (in polynomial time) verify that the solution is correct.
- Every problem in NP can be converted or reduced to a problem in NP-complete. Note that since all NP-complete problems are also in NP, by definition NP-complete problems can be reduced to each other also.

The second property allows us to say that if we can solve a problem * A* quickly, and another problem

**can be transformed into problem**

*B***, then we can also solve**

*A***quickly. The caveat here is that the transformation itself should take polynomial time. If the transformation takes superpolynomial time then it defeats the purpose of transforming in the first place.**

*B*Both the graph coloring and subset sum problems are NP-complete, but string-matching isn't. Other notable NP-complete problems include:

Clique problem: A clique consists of a subset of those vertices in a graph, where each vertex is connected to every other vertex within the set. The goal is to find the maximum clique in a graph.

Hamiltonian path problem: Given an undirected graph is there a path in the graph that visits each vertex exactly once?

Sudoku: Solving a sudoku puzzle isn't polynomial time activity, whereas if given a solution to a Sudoku puzzle, the correctness can be verified in polynomial time.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.