Types of Complexity Classes |

P, NP, CoNP, NP hard and NP complete

In computer science, there exist some problems whose solutions are not yet found, the
problems are divided into classes known as Complexity Classes. In complexity theory, a
Complexity Class is a set of problems with related complexity. These classes help scientists
to groups problems based on how much time and space they require to solve problems and
verify the solutions. It is the branch of the theory of computation that deals with the
resources required to solve a problem.
The common resources are time and space, meaning how much time the algorithm takes to
solve a problem and the corresponding memory usage.
The time complexity of an algorithm is used to describe the number of steps required to solve
a problem, but it can also be used to describe how long it takes to verify the answer.
The space complexity of an algorithm describes how much memory is required for the
algorithm to operate.
Complexity classes are useful in organizing similar types of problems.
Types of Complexity Classes
This article discusses the following complexity classes:
1. P Class
2. NP Class
3. CoNP Class
4. NP hard
5. NP complete

P Class
The P in the P class stands for Polynomial Time. It is the collection of decision
problems(problems with a “yes” or “no” answer) that can be solved by a deterministic
machine in polynomial time.
Features:
1. The solution to P problems is easy to find.
2. P is often a class of computational problems that are solvable and tractable. Tractable
means that the problems can be solved in theory as well as in practice. But the problems
that can be solved in theory but not in practice are known as intractable.
This class contains many natural problems like:
1. Calculating the greatest common divisor.
2. Finding a maximum matching.
3. Decision versions of linear programming.

NP Class
The NP in NP class stands for Non-deterministic Polynomial Time. It is the collection of
decision problems that can be solved by a non-deterministic machine in polynomial time.
Features:
1. The solutions of the NP class are hard to find since they are being solved by a non-
deterministic machine but the solutions are easy to verify.
2. Problems of NP can be verified by a Turing machine in polynomial time.
Example:
Let us consider an example to better understand the NP class. Suppose there is a company
having a total of 1000 employees having unique employee IDs. Assume that there are 200
rooms available for them. A selection of 200 employees must be paired together, but the
CEO of the company has the data of some employees who can’t work in the same room due
to some personal reasons.
This is an example of an NP problem. Since it is easy to check if the given choice of 200
employees proposed by a coworker is satisfactory or not i.e. no pair taken from the coworker
list appears on the list given by the CEO. But generating such a list from scratch seems to be
so hard as to be completely impractical.
It indicates that if someone can provide us with the solution to the problem, we can find the
correct and incorrect pair in polynomial time. Thus for the NP class problem, the answer is
possible, which can be calculated in polynomial time.
This class contains many problems that one would like to be able to solve effectively:
1. Boolean Satisfiability Problem (SAT).
2. Hamiltonian Path Problem.
3. Graph coloring.

Co-NP Class
Co-NP stands for the complement of NP Class. It means if the answer to a problem in Co-NP
is No, then there is proof that can be checked in polynomial time.
Features:
1. If a problem X is in NP, then its complement X’ is also is in CoNP.
2. For an NP and CoNP problem, there is no need to verify all the answers at once in
polynomial time, there is a need to verify only one particular answer “yes” or “no” in
polynomial time for a problem to be in NP or CoNP.
Some example problems for C0-NP are:
1. To check prime number.
2. Integer Factorization.

NP-hard class
An NP-hard problem is at least as hard as the hardest problem in NP and it is the class of the
problems such that every problem in NP reduces to NP-hard.
Features:
1. All NP-hard problems are not in NP.
2. It takes a long time to check them. This means if a solution for an NP-hard problem is
given then it takes a long time to check whether it is right or not.
3. A problem A is in NP-hard if, for every problem L in NP, there exists a polynomial-time
reduction from L to A.
Some of the examples of problems in Np-hard are:
1. Halting problem.
2. Qualified Boolean formulas.
3. No Hamiltonian cycle.

NP-complete class
A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard
problems in NP.
Features:
1. NP-complete problems are special as any problem in NP class can be transformed or
reduced into NP-complete problems in polynomial time.
2. If one could solve an NP-complete problem in polynomial time, then one could also solve
any NP problem in polynomial time.
Some example problems include:
1. Decision version of 0/1 Knapsack.
2. Hamiltonian Cycle.
3. Satisfiability.
4. Vertex cover.

Complexity
Class Characteristic feature

P Easily solvable in polynomial time.

NP Yes, answers can be checked in polynomial time.

Co-NP No, answers can be checked in polynomial time.

All NP-hard problems are not in NP and it takes a long time to

NP-hard check them.

NP-complete A problem that is NP and NP-hard is NP-complete.

 Introduction to NP-Completeness
We have been writing about efficient algorithms to solve complex problems, like shortest
path, Euler graph, minimum spanning tree, etc. Those were all success stories of algorithm
designers. In this post, failure stories of computer science are discussed.

Can all computational problems be solved by a computer?

There are computational problems that cannot be solved by algorithms even with unlimited time.
For example Turing Halting problem (Given a program and an input, whether the program will
eventually halt when run with that input, or will run forever). Alan Turing proved that a general
algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key
part of the proof is, that the Turing machine was used as a mathematical definition of a computer
and program (Source Halting Problem).

Status of NP-Complete problems is another failure story, NP-complete problems are problems
whose status is unknown. No polynomial-time algorithm has yet been discovered for any NP-
complete problem, nor has anybody yet been able to prove that no polynomial-time algorithm
exists for any of them. The interesting part is, that if any one of the NP-complete problems can
be solved in polynomial time, then all of them can be solved.

What are NP, P, NP-complete, and NP-Hard problems?

P is a set of problems that can be solved by a deterministic Turing machine in Polynomial-time.

NP is a set of decision problems that can be solved by a Non-deterministic Turing Machine in

Polynomial-time. P is a subset of NP (any problem that can be solved by a deterministic machine
in polynomial time can also be solved by a non-deterministic machine in polynomial time).
Informally, NP is a set of decision problems that can be solved by a polynomial-time via a
“Lucky Algorithm”, a magical algorithm that always makes a right guess among the given set of
choices (Source Ref 1).

NP-complete problems are the hardest problems in the NP set. A decision problem L is NP-
complete if:
1) L is in NP (Any given solution for NP-complete problems can be verified quickly, but there is
no efficient known solution).
2) Every problem in NP is reducible to L in polynomial time (Reduction is defined below).

A problem is NP-Hard if it follows property 2 mentioned above, and doesn’t need to follow
property 1. Therefore, the NP-Complete set is also a subset of the NP-Hard set.
 Decision vs Optimization Problems

NP-completeness applies to the realm of decision problems. It was set up this way because it’s
easier to compare the difficulty of decision problems than that of optimization problems. In
reality, though, being able to solve a decision problem in polynomial time will often permit us to
solve the corresponding optimization problem in polynomial time (using a polynomial number of
calls to the decision problem). So, discussing the difficulty of decision problems is often really
equivalent to discussing the difficulty of optimization problems. (Source Ref 2).
For example, consider the vertex cover problem (Given a graph, find out the minimum sized
vertex set that covers all edges). It is an optimization problem. The corresponding decision
problem is, given undirected graph G and k, is there a vertex cover of size k?

What is Reduction?
Let L1 and L2 be two decision problems. Suppose algorithm A2 solves L2. That is, if y is an input
for L2 then algorithm A2 will answer Yes or No depending upon whether y belongs to L2 or not.
The idea is to find a transformation from L1 to L2 so that algorithm A2 can be part of an
algorithm A1 to solve L1.
Learning reduction, in general, is very important. For example, if we have library functions to
solve certain problems and if we can reduce a new problem to one of the solved problems, we
save a lot of time. Consider the example of a problem where we have to find the minimum
product path in a given directed graph where the product of the path is the multiplication of
weights of edges along the path. If we have code for Dijkstra’s algorithm to find the shortest
path, we can take the log of all weights and use Dijkstra’s algorithm to find the minimum
product path rather than writing a fresh code for this new problem.

How to prove that a given problem is NP-complete?

From the definition of NP-complete, it appears impossible to prove that a problem L is NP-
Complete. By definition, it requires us to that show every problem in NP is polynomial time
reducible to L. Fortunately, there is an alternate way to prove it. The idea is to take a known
NP-Complete problem and reduce it to L. If a polynomial-time reduction is possible, we can
prove that L is NP-Complete by transitivity of reduction (If an NP-Complete problem is
reducible to L in polynomial time, then all problems are reducible to L in polynomial time).

What was the first problem proved as NP-Complete?

There must be some first NP-Complete problem proved by the definition of NP-Complete
problems. SAT (Boolean satisfiability problem) is the first NP-Complete problem proved by
Cook (See CLRS book for proof).

Difference between NP hard and NP complete problem

Prerequisite: NP-Completeness

NP Problem:

The NP problems set of problems whose solutions are hard to find but easy to verify and are
solved by Non-Deterministic Machine in polynomial time.

NP-Hard Problem:
A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is reducible to X in
polynomial time. NP-Hard problems are as hard as NP-Complete problems. NP-Hard Problem
need not be in NP class.

If every problem of NP can be polynomial time reduced to it called as NP Hard.

A lot of times takes the particular problem solve and reducing different problems.

example:

1. Hamiltonian cycle.
 2. Optimization problem.

3. Shortest path

NP-Complete Problem:

A problem X is NP-Complete if there is an NP problem Y, such that Y is reducible to X in

polynomial time. NP-Complete problems are as hard as NP problems. A problem is NP-
Complete if it is a part of both NP and NP-Hard Problem. A non-deterministic Turing machine
can solve NP-Complete problem in polynomial time.

A problem is np-complete when it is both np and np hard combines together.

This means np complete problems can be verified in polynomial time.

Example:

1. Decision problems.

2. Regular graphs.

Difference between NP-Hard and NP-Complete:

NP-Hard NP-Complete

NP-Hard problems(say X) can be solved if

and only if there is a NP-Complete NP-Complete problems can be solved by a non-
problem(say Y) that can be reducible into X deterministic Algorithm/Turing Machine in
in polynomial time. polynomial time.

To solve this problem, it do not have to be To solve this problem, it must be both NP and
in NP . NP-hard problems.

Time is unknown in NP-Hard. Time is known as it is fixed in NP-Hard.

NP-hard is not a decision problem. NP-Complete is exclusively a decision problem.

Not all NP-hard problems are NP-complete. All NP-complete problems are NP-hard
 NP-Hard NP-Complete

Do not have to be a Decision problem. It is exclusively a Decision problem.

It is optimization problem used. It is Decision problem used.

Example: Determine whether a graph has a

Hamiltonian cycle, Determine whether a Boolean
Example: Halting problem, Vertex cover formula is satisfiable or not, Circuit-satisfiability
problem, etc. problem, etc.