Nondeterminism

from Wikipedia, the free encyclopedia

Nondeterminism is a concept from theoretical computer science in which algorithms or machines (mostly Turing machines or finite automata ) can not only run through exactly one calculation for a certain input ( deterministic ), but with the same input there are several possibilities for the transition to the following state gives. The program of the respective machine does not in any way specify which of the options must be selected. In the analysis of such algorithms, however, it is always assumed that the best possible transition has been selected in the respective context.

Nondeterministic machines are theoretical models and generally not practicable. Its purpose in theoretical computer science is to limit the complexity of problems upwards, which means that a problem for which one can specify a nondeterministic algorithm is "easier" than a problem for which one cannot. In many cases it is easier to find a nondeterministic algorithm for a problem than a deterministic (and thus practically realizable) algorithm. It is therefore an important question in theoretical computer science under which circumstances one can efficiently simulate nondeterministic algorithms or machines by means of deterministic algorithms or machines.

Acceptance of nondeterministic algorithms

As a rule, non-deterministic algorithms or machines are only considered for decision problems . For inputs for which the answer is no , the algorithm must deliver the answer no regardless of the nondeterministic choice of the calculation method. For inputs for which the answer is yes , there must be at least one calculation method so that the algorithm delivers the answer yes (while it can also provide the answer no on other calculation methods ).

Examples

One area where nondetermism occurs naturally is in the description of formal languages ​​through grammars . Let G a grammar for a formal language L . If a word w belongs to L , there is a derivation for w in grammar; if a word w does not belong to L , it applies to all derivations in grammar that they do not yield the word w . Therefore the automaton models belonging to grammars are usually nondeterministic.

As a more concrete example of a nondeterministic algorithm, we consider the test of whether a given graph G = (V, E) contains a Hamilton cycle, i.e. a cycle that contains every node of the graph exactly once. A nondeterministic algorithm works as follows: It writes (nondeterministically) a sequence of numbers from the set . Then he tests whether each of the numbers from the set occurs exactly once in the sequence. Finally, it is tested whether the edges and occur in the graph. If all tests are 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 will be yes : in the nondeterministic phase, if the algorithm writes the nodes in the order of the Hamilton cycle, all tests are positive and the answer is yes . If the graph does not contain a Hamilton cycle, there is no way all tests will be positive, so the answer is no .

This example also shows for which decision problems nondeterministic algorithms can easily be found. These are the problems that ask about the existence of a solution, where given a solution it is easy to check that the solution is correct, but it may be difficult to compute the solution directly. In the example the solution is the Hamilton cycle; for a given knot sequence it is easy to test whether it forms a Hamilton cycle, while it is much more difficult to find a Hamilton cycle. This problem “circumvent” nondeterministic algorithms, since with them it is not necessary to specify how to get the solution.

Illustrations of nondeterminism

Since nondeterministic algorithms cannot be implemented on real computers and are therefore very difficult to visualize, nondeterminism is often referred to as “guessing” in textbooks. I.e. for example, for the example above, that the nondeterministic algorithm “guesses” the Hamilton cycle and then verifies that what it has guessed is really a Hamilton cycle. On the one hand, this perspective leads to a simpler description of nondeterministic algorithms, but on the other hand it also leads to misunderstandings and misinterpretations if the correctness is not explicitly checked as in the example above.

Another illustration is to take nondeterminism as a generalization of randomized algorithms . Instead of choosing non-deterministically between different calculation steps, it is simply rolled out (with the help of random numbers) which calculation step is selected. The above-described mode of acceptance of nondeterministic algorithms is then described in terms of success probabilities as follows: If the correct answer is no , the probability that the algorithm will output no is equal to 1; if the correct answer is yes , the algorithm is more likely than zero to say yes . The latter corresponds to the existence of a calculation method on which the algorithm delivers the answer yes .

Comparison of nondeterministic and deterministic calculation models

For some calculation models, simulations of the nondeterministic variants using the deterministic variants are possible. These are in particular Turing machines with no restrictions on computing time and storage space, as well as finite automata . For other calculation models it can be shown that the nondeterministic variant can calculate a larger class of problems than the deterministic variant. These are in particular the so-called push -down machines , as well as models from communication complexity .

In complexity theory is also examined the extent to which non-determinism to the order of necessary resources (such as run-time or memory consumption effect). This question has not yet been clarified. This applies in particular to the polynomial time-limited Turing machines (or polynomial time-limited algorithms). The set of decision problems with polynomial time-constrained nondeterministic algorithms is called NP (NP stands for nondeterministic polynomial ); the set of decision problems with polynomial time-constrained deterministic algorithms is denoted as P. Obviously applies . The question of whether these two complexity classes are the same 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 question arises from the fact that many practically important problems are of the type described above, i.e. that the correctness of a solution can be easily checked, but it is probably difficult to calculate a correct solution.

literature