HOME

TheInfoList



OR:

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, the Immerman–Szelepcsényi theorem states that nondeterministic space
complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
es are closed under complementation. It was proven independently by
Neil Immerman Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.
and
Róbert Szelepcsényi Róbert Szelepcsényi (; born 19 August 1966, Žilina) is a Slovak computer scientist of Hungarian descent and a member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava. His results on the closure of ...
in 1987, for which they shared the 1995
Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interes ...
. In its general form the theorem states that
NSPACE In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE. Complexity classes The mea ...
(''s''(''n'')) = co-NSPACE(''s''(''n'')) for any function ''s''(''n'') ≥ log ''n''. The result is equivalently stated as NL = co-NL; although this is the special case when ''s''(''n'') = log ''n'', it implies the general theorem by a standard
padding argument In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal. Example The proof that P =  NP implies EXP =&nbs ...
. The result solved the second LBA problem. In other words, if a nondeterministic machine can solve a problem, another machine with the same resource bounds can solve its
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
problem (with the ''yes'' and ''no'' answers reversed) in the same asymptotic amount of space. No similar result is known for the
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
classes, and indeed it is conjectured that NP is not equal to
co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
. The principle used to prove the theorem has become known as inductive counting. It has also been used to prove other theorems in computational complexity, including the closure of
LOGCFL In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is situated between NL and AC1, in the sense that it contains th ...
under complementation and the existence of error-free randomized logspace algorithms for
USTCON In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (''undirected s-t connectivity''), which is the problem of determining whether there exists a path between two ve ...
..


Proof sketch

The theorem can be proven by showing how to translate any nondeterministic Turing machine ''M'' into another nondeterministic Turing machine that solves the complementary
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
under the same (asymptotic) space complexity, plus a constant number of pointers and counters, which needs only a
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
ic amount of space. The idea is to simulate all the configurations of ''M'' on input ''w'', and to check if any configuration is accepting. This can be done within the same space plus a constant number of pointers and counters to keep track of the configurations. If no configuration is accepting, the simulating Turing machine accepts the input ''w''. This idea is elaborated below for logarithmic NSPACE class ( NL), which generalizes to larger NSPACE classes via a
padding argument In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal. Example The proof that P =  NP implies EXP =&nbs ...
. The configuration of ''M'' consists of the state, the position of the head on the tape, and the logarithmically-sized contents of the tape. A configuration can be thought of as the vertex of a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
, and the transitions of ''M'' can be thought of as edges in this graph. ''M'' accepts an input string whenever there exists a path in this graph from the vertex , which represents the starting configuration, to a special vertex that represents ''any'' accepting configuration. Checking whether an input ''w'' is accepted by ''M'' then reduces to -connectivity problem for the
implicit graph In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from so ...
represented by the input Turing machine ''M''. Likewise, if we wish to compute the complement of ''L(M)'' (the language recognized by ''M''), we accept only when there does ''not'' exist a path from to in the input graph. An algorithm that solves this non-reachability problem can be based on the principle of counting, for each number from 1 to (the order of the implicit graph), the number of vertices reachable from by paths of length at most . If, at any stage of the algorithm, the correct value of is known for some value of , then it is possible to test whether a given vertex is reachable from by paths of length at most , using the following subroutine: #If , return true #Initialize a counter to 0 #For each vertex in the implicit graph, repeat the following steps: #*Nondeterministically search for a path of length at most from to #*If a path to is found, increment and test whether there exists an edge from to #If , halt the algorithm and reject the input. Otherwise, return true if an edge from to was found, and false otherwise. When used within a larger nondeterministic algorithm, the only accepting computations of the algorithm can be ones in which the subroutine finds paths to all the reachable vertices and computes the correct answer, so this subroutine can be used as if it were deterministic. With it in hand, the algorithm for testing non-reachability of ''t'' from ''s'' can be expressed by the following steps. (As above, is the number of vertices reachable from by paths of length at most .) #Initialize to 0 and to 1 #Repeat the following steps times: #*Initialize a counter to 0 #*For each vertex test whether is reachable from within steps, and if so increment #*Increment and set to #Test whether is reachable from within steps, and reject the input if it is; otherwise, accept the input. The algorithm only needs to maintain representations of a constant number of counters and vertices in its memory, so it uses logarithmic space. By applying this algorithm to the implicit graph constructed from a given nondeterministic machine ''M'', one obtains a nondeterministic machine for the complementary language to the one accepted by ''M''.


Logspace hierarchy

As a corollary, in the same article, Immerman proved that, using
descriptive complexity ''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of lo ...
's equality between NL and FO(Transitive Closure), the logarithmic hierarchy, i.e. the languages decided by an alternating Turing machine in logarithmic space with a bounded number of alternation, is the same class as NL.


See also

* Savitch's theorem relates nondeterministic space classes to their deterministic counterparts


Notes


References

* *


External links

* Lance Fortnow,
Foundations of Complexity, Lesson 19: The Immerman–Szelepcsenyi Theorem
'' Accessed 09/09/09. {{DEFAULTSORT:Immerman-Szelepcsenyi theorem Structural complexity theory Mathematical theorems in theoretical computer science Articles containing proofs