Deterministic and Non-Deterministic Algorithms: Sr. No. Key Deterministic Algorithm Non-Deterministic Algorithm

Deterministic and Non-Deterministic Algorithms
In the context of programming, an Algorithm is a set of well-defined instructions

in sequence to perform a particular task and achieve the desired output. Here we
say set of defined instructions which means that somewhere user knows the
outcome of those instructions if they get executed in the expected manner.
On the basis of the knowledge about outcome of the instructions, there are two
types of algorithms namely − Deterministic and Non-deterministic Algorithms.
Following are the main differences between both of the algorithms –
Sr. Key Deterministic Algorithm Non-deterministic

No. Algorithm
1 Definition The algorithms in which the result of On other hand, the

every algorithm is uniquely defined are algorithms in which the
known as the Deterministic Algorithm. result of every algorithm is
In other words, we can say that the not uniquely defined and
deterministic algorithm is the algorithm result could be random are
that performs fixed number of steps and known as the Non-
always get finished with an accept or Deterministic Algorithm.
reject state with the same result.
2 Execution In Deterministic Algorithms execution, On other hand in case of

the target machine executes the same Non-Deterministic
instruction and results same outcome Algorithms, the machine
which is not dependent on the way or executing each operation is
process in which instruction get allowed to choose any one
executed. of these outcomes subjects
to a determination condition
to be defined later.
3 Type On the basis of execution and outcome On other hand Non

in case of Deterministic algorithm, they deterministic algorithm are
are also classified as reliable algorithms classified as non-reliable
Sr. Key Deterministic Algorithm Non-deterministic
No. Algorithm
as for a particular input instructions the algorithms for a particular

machine will give always the same input the machine will give
output. different output on different
executions.
4 Execution As outcome is known and is consistent On other hand as outcome is

Time on different executions so Deterministic not known and is non-
algorithm takes polynomial time for consistent on different
their execution. executions so Non-
Deterministic algorithm
could not get executed in
polynomial time.
5 Execution In deterministic algorithm the path of On other hand in case of

path execution for algorithm is same in Non-Deterministic
every execution. algorithm the path of
execution is not same for
algorithm in every
execution and could take
any random path for its
execution.
Non-deterministic algorithms are useful for finding approximate solutions, when

an exact solution is difficult or expensive to derive using a deterministic algorithm.
Time Complexity Classes

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 hardest 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. 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

NP-hard to check them.
NP-complete A problem that is NP and NP-hard is NP-complete.

Deterministic and Non-Deterministic Algorithms: Sr. No. Key Deterministic Algorithm Non-Deterministic Algorithm

Uploaded by

Copyright:

Available Formats

Deterministic and Non-Deterministic Algorithms: Sr. No. Key Deterministic Algorithm Non-Deterministic Algorithm

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Deterministic and Non-Deterministic Algorithms: Sr. No. Key Deterministic Algorithm Non-Deterministic Algorithm

Uploaded by

Copyright:

Available Formats

Deterministic and Non-Deterministic Algorithms

In the context of programming, an Algorithm is a set of well-defined instructions

Sr. Key Deterministic Algorithm Non-deterministic

1 Definition The algorithms in which the result of On other hand, the

2 Execution In Deterministic Algorithms execution, On other hand in case of

3 Type On the basis of execution and outcome On other hand Non

as for a particular input instructions the algorithms for a particular

4 Execution As outcome is known and is consistent On other hand as outcome is

5 Execution In deterministic algorithm the path of On other hand in case of

Non-deterministic algorithms are useful for finding approximate solutions, when

Time Complexity Classes

The P in the P class stands for Polynomial Time. It is the collection of decision

A problem is NP-complete if it is both NP and NP-hard. NP-complete problems

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

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

You might also like