Deterministic vs. Nondeterministic Computations
Table of content
”;
To understand class P and NP, first we should know the computational model. Hence, in this chapter we will discuss two important computational models.
Deterministic Computation and the Class P
The deterministic computation always provides the same output during the initial state with all the data available. As long as there is no change in the computation, there is no randomness involved with it.
There are various models available to perform deterministic computation −
Deterministic Turing Machine
One of these models is deterministic one-tape Turing machine. This machine consists of a finite state control, a read-write head and a two-way tape with infinite sequence.
Following is the schematic diagram of a deterministic one-tape Turing machine.
A program for a deterministic Turing machine specifies the following information −
- A finite set of tape symbols (input symbols and a blank symbol)
- A finite set of states
- A transition function
In algorithmic analysis, if a problem is solvable in polynomial time by a deterministic one tape Turing machine, the problem belongs to P class.
Nondeterministic Computation and the Class NP
Nondeterministic Turing Machine
To solve the computational problem, another model is the Non-deterministic Turing Machine (NDTM). The structure of NDTM is similar to DTM, however here we have one additional module known as the guessing module, which is associated with one write-only head.
Following is the schematic diagram.
If the problem is solvable in polynomial time by a non-deterministic Turing machine, the problem belongs to NP class.
”;