P-Class

●​ The class P consists of those problems that are solvable in polynomial time, i.e.
these problems can be solved in time O(n k) in the worst-case, where k is
constant.
●​ These types of problems are called tractable and others are called intractable or
super polynomial.
●​ Generally, an algorithm is a polynomial time algorithm, if there exists a polynomial
p(n) such that the algorithm can solve any instance of size n in a time O(p(n)).
●​ Problems requiring Ω(n 50) time to solve are essentially intractable for large n.
Most known polynomial time algorithms run in time O(n^k) for a fairly low value of
k.
●​ The advantage in the class of polynomial-time algorithms is that all reasonable
deterministic single processor models of computation can be simulated on each
other with at most a polynomial slow-d.
NP-Class
●​ The class NP consists of problems that are verifiable in polynomial time. NP is a
class of decision problems for which it is easy to check the correctness of a given
answer, with the aid of a little extra information. Hence, we are not asking for a
way to find a solution, but only to verify that a solution really is correct.
●​ Every problem in the given class can be solved in exponential time using
exhaustive search.
Example
Consider an example to check if a problem is in P class or NP class
Step 1 − If a problem is in class P, it is nothing but we can find a solution to that type of
problem in polynomial time.
Step 2 − If a problem is in class NP, it is nothing but that we can verify a possible
solution in polynomial time.
Step 3− Consider another way, NP means that a problem is
NondeterministicallyPolynomial. Specifically, that means that if you could build a
machine that had the ability to try all the possible solutions of your problem at once, it
could finish in polynomial time.
We know this to be true because we know that we can verify a possible solution in
polynomial time, and what that machine is basically doing is trying to verify (test) all of
the potential answers to the problem at the same time.
Step 4 − So, if you can solve a problem in polynomial time, you can certainly verify that
your answer is correct in polynomial time, can't you? Sure, if you can prove that your
algorithm is correct and that it can find an answer in polynomial time, which it must to
be in P.
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 group 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:
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 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 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 a class of
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 Characteristic feature
Class
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.

Following are the differences between the P class problem and the NP class problem:

Sr. P class Problem NP class Problem

No
1. P problems are a set of problems that NP problems are problems that can be solved in
can be solved in polynomial time by nondeterministic polynomial time.
deterministic algorithms.
2. P Problems can be solved and verified The solution to NP problems cannot be obtained in
in polynomial time. polynomial time, but if the solution is given, it can
be verified in polynomial time.
3. P problems are a subset of NP NP Problems are a superset of P problems.
problems.
4. All P problems are deterministic in All the NP problems are non-deterministic in
nature. nature.
5. It takes polynomial time to solve a It takes non-deterministic polynomial time to
problem like n, n^2, n*logn, etc. quickly check a problem.
6. The solution to P class problems is The solution to NP class problems is hard to find.
easy to find.
7. Examples of P problems are: Selection Examples of NP problems are the Travelling
sort, Linear Search salesman problem and the knapsack problem.