# 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:**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions