Home »
Algorithms
Deterministic and Non Deterministic Algorithms
In this article, we are going to learn about the undecidable problems, polynomial and non - polynomial time algorithms, and the deterministic, non - deterministic algorithms.
Submitted by Shivangi Jain, on July 25, 2018
Undecidable Problems
An undecidable problem is a problem for which there is no algorithm that can solve it. Alan Turing proved that the famous halting problem is undecidable. The halting problem can be simply stated as follows - Given an input and a Turing machine, there is no algorithm to determine if the machine will eventually halt. There are several problems in mathematics and computer science that are undecidable.
Polynomial and Non - polynomial time algorithm
If the complexity of an algorithm is expressed as O (p(n)) where p(n) is some polynomial of n, then the algorithm is said to be a polynomial time algorithm. Generally, polynomial time algorithms are tractable. Any algorithm with a time complexity that cannot be bounded by such bound then this is known as non - polynomial algorithms.
Deterministic and Non - deterministic Algorithms
The algorithms in which the result of every algorithm is uniquely defined are known as the deterministic algorithm. In the theoretical framework, we can remove this restriction on the outcome of every operation. We can allow algorithms to contain operations whose outcomes are not uniquely defined but are limited to specified sets of possibilities. The machine executing each operation is allowed to choose any one of these outcomes subjects to a determination condition to be defined later. This leads to the concept of a Non-deterministic algorithm.
There are three new functions which specify such types of algorithms are:
- Choice(S) arbitrarily chooses one of the elements of the set S.
- Failure() signals an unsuccessful completion.
- Success() signals a successful completion.
The assignments statement x: Choice (1, n) could result in x being assigned any one of the integers in the range [1, n]. There is no rule specifying how this choice is to be made. The Failure() and the Success() signals are used to define a computation of the algorithm. These statements cannot be used to effect a return. Whenever there is a set of the choices that lead to a successful completion, then one such set of the choices is always made and the algorithm terminates successfully. A non - deterministic algorithm terminates unsuccessfully if and only if there exists no set of the choices leading to a success signal. The computing times for the Choices, the Success, and the Failure are taken to be O (1). A machine capable of executing a non - deterministic algorithm in this way is called a non – deterministic machine.
References: