Immerman and Szelepcsényi's theorem

from Wikipedia, the free encyclopedia

The set of Immerman and Szelepcsényi is a sentence from the complexity theory and states that the non-deterministic space complexity classes are closed under complementation. In particular, therefore, the class NL (nondeterministic logarithmic space) is completed with complement formation.

As for the nondeterministic time complexity classes , it was long assumed that NL was not closed under the complement, until Immerman and Szelepcsényi independently provided the proof in 1988. For this, both of them would be awarded the Gödel Prize (1995).

Formal definition

Let be a monotonic function with . Then:

In particular then applies . But it is also true that the theorem follows for everyone with the padding technique .

proof

The proof uses the proof technique of (nondeterministic) inductive counting.

Preliminary remarks

Be a language above type 1 grammar with the usual symbols for non-terminals , terminals , production rules and the start symbol . Then for a word the graph is that graph that contains all sentence forms with a length at most the length of , whereby the graph has an edge between two sentence forms if and only if there is a production in . In particular, the graph contains both and itself, and it holds that if and only if there is a path from to in this graph.

If it is now possible to construct a nondeterministic, linearly bounded Turing machine that accepts if and only if there is no path from to , the proof has been given.

Unavailability

First it is assumed that the number of nodes that can be reached is known from (we postpone the calculation from until later). Then the following algorithm solves the inaccessibility.

Given graph , start node , target node and number of reachable nodes .

  1. Initialize counter
  2. For each node :
    • Non- deterministic guess whether from is reachable and if the answer is positive:
      • Rate is not deterministic of a path according to the length of a maximum and
      • if the path was wrong or does not lead to , break off with no ,
      • if , cancel with no (because the node is obviously reachable),
      • otherwise increase the counter by one.
  3. If so , cancel with no , otherwise output yes .

Neither nor can it be larger than and therefore (in binary code) do not consume more than memory space. The algorithm ensures that all nodes that can be reached from are enumerated and only accepts if none of these nodes was.

Inductive counting

All that remains is to determine the previously unknown number of nodes that can be reached. The idea is to calculate the number of nodes that can be reached in at most steps. You can then count up inductively and use that applies. The algorithm works as follows:

  1. Initialize (the start node does not need a step to be reached)
  2. For any number of steps :
    1. Initialize .
    2. For each node :
      1. Initialize a counter
      2. For each node :
        • Whether rate not deterministic of in less than is achievable steps.
        • If so, guess a path with a length smaller and abort if the path does not end in.
        • If such a path was found, increase the counter by one and ...
        • ... if equals or there is a knate from to , also increase by one and continue the iteration from (marked with ).
      3. If so , cancel the calculation
  3. Give back.

Since the algorithm only needs to remember three counters ( ) at the same time, it can be implemented with logarithmic storage space. Formal proof of correctness is left to the interested reader. The following hint serves as a proof idea: it is not incremented if and only if all nodes with a distance smaller than tried and no further nodes that can be reached directly (i.e. in at most one step) could be found.

The proof

Now only both algorithms have to be combined.

  1. Calculate for and through inductive counting.
  2. Use unavailability for and with previously calculated .

Such a Turing machine accepts if and only if there is no path from to and since both sub-algorithms only require logarithmic storage space, the proof is complete.

See also

literature

Original publications:

Textbooks: