Nondeterministic algorithm

Non-determinism is a concept from the theoretical computer science, in the algorithms or machines (usually Turing machines or finite automata ) can not only accurately through a calculation to a particular input ( deterministic), but with the same input several options for the transition to the next state there. This is dictated by the program of each machine in any way, which must be chosen by the facility. In the analysis of such algorithms, but is then always assumed that in context, the best possible transition is selected.

Nondeterministic machines are theoretical models and generally not practically feasible. Their purpose in theoretical computer science is to limit the complexity of problems up, that means that a problem for which you can specify a non- deterministic algorithm that is "easier" than a problem for which you can not. In many cases it is easier for a problem to find a non-deterministic algorithm as a deterministic (and therefore practically feasible ) algorithm. Therefore, it is an important issue in theoretical computer science, in what circumstances one can simulate non-deterministic algorithms or machines efficiently by deterministic algorithms or machines.

Acceptance of non-deterministic algorithms

Nondeterministic algorithms or machines are usually considered only for decision problems. For entries, for the answer is no, the algorithm must be independent of the non-deterministic choice of the calculation course provide the answer is no. For entries, for the answer is Yes, there must be at least one computation path, so that the algorithm provides the answer is yes ( as he must deliver to other computing paths and the answer is no ).

Examples

One area in which Nichtdetermismus occurs naturally, is the description of formal languages ​​by grammars. Let G be a grammar for a formal language L. If a word w belongs to L, there is a derivation for w in the grammar; if a word w does not belong to L, valid for all derivations in the grammar that they do not deliver the word w. Therefore, belonging to grammars automata models are usually not deterministic.

As a concrete example of a non-deterministic algorithm, we consider the test for whether a given graph G = (V, E) contains a Hamilton cycle, ie a cycle containing every vertex of the graph exactly once. A non- deterministic algorithm proceeds as follows: He writes ( nondeterministic ) is a sequence of numbers from the set. He then tests whether each of the numbers from the set in the sequence appears exactly once. Finally, it is checked whether the edges found in the graph. If all tests go positive, the output is Yes, otherwise No.

For correctness: If the given graph G contains a Hamilton cycle, there is a possibility that the output is yes: If the algorithm is not deterministic phase writes down the nodes in the order of the Hamilton cycle, all the tests go positive and the answer is yes. When the graph does not contain a Hamiltonian cycle, there is no possibility that all of the tests are positive, so the answer is no.

This example also shows which decision problems easily nondeterministic algorithms can be found. These are the problems, which asked about the existence of a solution, it is easy for a given solution to check whether the solution is correct, and it is but may be difficult to calculate the solution directly. In the example, the solution of the Hamilton county; for a given knot sequence one can easily test whether it forms a Hamilton cycle, while it is much more difficult to find a Hamilton cycle. This problem "bypass" non-deterministic algorithms, since they need not be specified, as they come to the solution.

Illustrations of nondeterminism

Since non-deterministic algorithms are not feasible on real computers, and thus are quite non-descriptive, non-determinism in textbooks is often referred to as " rates " means. That is, for example, for the example above that the non-deterministic algorithm to Hamilton Circle " advises " and then verifies that what he advised, really is a Hamilton cycle. This view also leads on one side to a simpler description of non- deterministic algorithms, on the other hand, to misunderstandings and misinterpretations if the accuracy is not explicitly checked in the example above.

Another illustration is to be regarded as a generalization of nondeterminism of randomized algorithms. Instead of choosing non-deterministically between various steps of calculation, is simply throwing dice (using random numbers ), which calculation step is chosen. The acceptance mode of non-deterministic algorithms described above is then described as follows by success probabilities: If the correct answer is no, then the probability that the algorithm outputs No, equal to 1; If the correct answer is yes, then the probability that the algorithm outputs Yes greater than zero. The latter corresponds to the existence of a processing path, on which the algorithm provides the answer is yes.

Comparison of non-deterministic and deterministic models of computation

For some models of computation simulations of the non-deterministic variations are possible due to the deterministic variants. These are in particular Turing machines without restrictions on computing time and memory, as well as finite automata. For other models of computation can be shown that the non-deterministic variant may charge a larger class of problems than the deterministic variant. These are in particular the so-called push-down automata, as well as models of communication complexity.

In complexity theory is also examined the extent to which non-determinism affects the magnitude of resources required ( such as running time or memory usage ). This question has not yet been clarified. This is particularly true for polynomially time bounded Turing machines (or polynomially time bounded algorithms). The set of decision problems with polynomial- time- bounded non-deterministic algorithms is known as NP (NP stands for nondeterministic polynomial ); the set of decision problems with polynomial- time bounded deterministic algorithms is known as P. Obviously applies. The question of whether these two complexity classes are identical or different, is known as the P- NP problem and is one of the most important open questions in theoretical computer science.

The importance of the issue arises from the fact that many practically important problems of the type described above are, so that the correctness of a solution is easily verifiable, but it's probably difficult to calculate a correct solution.

602366
de