Complexity Class of Algorithm for Beginner

In computer science, problems are divided into classes known as Complexity Classes. In complexity theory, a Complexity Class is a set of problems with related complexity. With the help of complexity theory, we try to cover the following.

Problems that cannot be solved by computers.
Problems that can be efficiently solved (solved in Polynomial time) by computers.
Problems for which no efficient solution (only exponential time algorithms) exist.

1. Complexity Theory
Complexity Classes
Manash Kumar Mondal
Department of Computer Science
Rani Rashmoni Green University
February 17, 2025
1 / 20

2. Overview
1.What is a Decision Problem?
2.What are Complexity Classes?
3.Importance of Complexity Classes
4.Types of Complexity Classes
5.Applications
2 / 20

3. What is a Decision Problem?
Definition
A decision problem is a question with a yes/no answer and the answer depends on the
values of input.
Examples
For example, the problem “Given an array of n numbers, check whether there are any
duplicates or not?” is a decision problem. The answer to this problem can be either yes or
no depending on the values of the input array.
3 / 20

4. What are Complexity Classes?
•There are some unsolvable problems in computer science, and those problems have
been divided into classes called complexity classes.
•In complexity theory, a Complexity Class is a set of problems with related complexity.
These classes help scientists in classifying difficulties according to the amount of time
and space needed 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.
4 / 20

5. What are Complexity Classes? (cont.)
A complexity class is a set of computational problems that have similar computational
requirements. The computational requirements can be defined in terms of the amount of
time, memory, or other resources required to solve a problem.
Complexity classes are usually classified based on the amount of resources required to
solve a problem in the class. These resources can be either time or space. Time
complexity refers to the number of steps required to solve a problem, whereas space
complexity refers to the amount of memory required to solve a problem.
5 / 20

6. Importance of Complexity Classes
1.It helps in understanding the difficulty of computational problems:Complexity
classes provide a theoretical framework for characterizing the difficulty of
computational problems based on the amount of resources required to solve them.
This helps in understanding the inherent complexity of a problem and in determining
the best algorithmic approach for solving it.
2.It helps in comparing different algorithms:Complexity classes provide a standard
benchmark for comparing the efficiency of different algorithms for solving the same
problem. This helps in selecting the most efficient algorithm for a given problem and
in assessing the practical feasibility of solving the problem.
6 / 20

7. Importance of Complexity Classes (cont.)
1.It helps in identifying intractable problems:Complexity classes help in identifying
problems that are computationally infeasible to solve in practice, such as
NP-Complete and NP-Hard problems. This can help in focusing research efforts on
developing approximation algorithms or heuristic methods for solving such problems.
2.It helps in understanding the limits of computation:Complexity classes provide
insights into the theoretical limits of computation, such as the fact that some
problems are inherently unsolvable or require an exponential amount of resources to
solve. This can help in developing new models of computation or in identifying new
research directions.
7 / 20

8. Types of Complexity Classes
•P Class
•NP Class
•CoNP Class
•NP-hard
•NP-complete
8 / 20

9. P(Polynomial Time) Class
‘P’ stands for Polynomial Time in the P class. 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:
•P-problem solutions are simple to find.
•P can be a class of feasible and solvable computing problems. It means that the
issues are both theoretically and practically solvable. However, unsolvable problems
are those that can be theoretically solved but cannot be practically solved.
There are various natural problems in this class:
•Finding the greatest common divisor.
•Finding the best possible match.
•Decision versions of linear programming.
9 / 20

10. NP(Non-Deterministic Polynomial Time) Class
NP stands for Non-deterministic Polynomial Time in the NP class. It is the set of decision
problems that can be solved in polynomial time by a non-deterministic machine.
Features:
•The NP class’s solutions are challenging to find because they are solved by a
non-deterministic machine, but they are simple to prove.
•A Turing machine can verify NP problems in polynomial time.
A lot of the problems in this class would be good to have able to solve efficiently:
•Graph coloring
•Boolean Satisfiability Problem (SAT).
•Hamiltonian Path Problem.
10 / 20

11. NP(Non-Deterministic Polynomial Time) Class (cont.)
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 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.
11 / 20

12. Co-NP Class
The term “Co-NP” refers to the NP Class’ complement. It indicates there is a proof that
can be verified in polynomial time if the solution to a Co-NP problem is No.
Features:
•If a problem X is in NP, then its complement X’ is also in CoNP.
•In order for a problem to be in NP or CoNP, only one specific answer — a “yes” or
“no” — needs to be verified in polynomial time, not all the solutions at once.
Examples of Co-NP problems include:
•Factorization of Integers.
•To verify Prime Numbers.
12 / 20

13. NP-hard Class
An NP-hard problem is at least as hard as the hardest problem in NP and it is a class of
problems such that every problem in NP reduces to NP-hard.
Features:
•Not all NP-hard problems are in NP.
•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
•If there is a polynomial-time reduction from problem L to problem A for every
problem L in NP, then problem A is NP-hard.
Some of the examples of problems in Np-hard are:
•No Hamiltonian cycle.
•Halting problem.
•Qualified Boolean formulas.
13 / 20

14. 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:
•Since any NP class problem can be converted into an NP-complete problem in a
polynomial time, NP-complete problems are unique.
•Any NP problem can be solved in polynomial time if one could solve an NP-complete
problem in that amount of time.
Some example problems include:
•Hamiltonian Cycle.
•Vertex cover.
•Decision version of 0/1 Knapsack.
14 / 20

15. Relationship between P, NP, Co-NP, NP-hard, and
NP-complete
Figure:Relationship between P, NP, Co-NP,
NP-hard, and NP-complete Figure:Relationship between P, NP, Co-NP,
NP-hard, and NP-complete
15 / 20

16. Relationship between P, NP, Co-NP, NP-hard, and
NP-complete(cont.)
Figure:Relationship between P, NP, Co-NP, NP-hard, and NP-complete
16 / 20

17. Summary
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.
NP-hard
All NP-hard problems are not in NP and it takes a long
time to check them.
NP-complete A problem that is NP and NP-hard is NP-complete.
17 / 20

18. Applications
Complexity theory has many practical applications in various fields. Here are some
examples:
•Optimization: Complexity theory is widely used in optimization problems, which
involve finding the best solution to a problem among a large number of possible
solutions. Optimization problems are common in many fields, such as engineering,
finance, logistics, and operations research. Complexity theory provides a framework
for analyzing the computational complexity of optimization algorithms and for
designing efficient algorithms that can solve these problems in a reasonable amount
of time.
•Game Theory: Complexity theory is also used in game theory, which studies the
interactions between rational decision-makers in strategic situations. Game theory is
used in many fields, such as economics, political science, and computer science.
Complexity theory provides a way to analyze the computational complexity of game
theory algorithms and to study the emergence of complexity in games with many
players and strategies.
18 / 20

19. Applications(cont.)
•Artificial Intelligence:Complexity theory is also important in the field of artificial
intelligence (AI). AI involves the development of algorithms and models that can
simulate human intelligence and behavior. Many AI algorithms involve complex
computations, and complexity theory provides a way to analyze the computational
complexity of these algorithms and to optimize their performance.
19 / 20

20. The End
20 / 20