 | This article needs additional citations for verification .(May 2016) |
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.[ citation needed ]
| | This article needs additional citations for verification .(May 2016) |
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.[ citation needed ]
A theoretical computational model, like Turing machine or finite automata, explains how to do a computation. The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop. A configuration, also called an Instantaneous Description (ID) is a finite representation of the machine at a given time. For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head. A configuration graph is a directed labeled graph where the label of the vertices are the possible configurations of the models and where there is an edge from one configuration to another if it correspond to a computational step of the model.[ citation needed ]
The initial and accepting configuration(s) of the machine are special vertices of the configuration graph. The computation accepts if and only if there is a path from an initial vertex to an accepting vertex.
If there exists exactly one initial state, then a computation is deterministic if and only if from any configuration there is at most one possible step, so if and only if the graph is of out-degree 1.[ citation needed ]
Once a dummy initial vertex with an edge to every initial vertex and a dummy accepting vertex with an edge from every accepting vertex are added, checking if there is an accepting computation only requires to check if there is a path from the initial vertex to the accepting vertex, which is the reachability problem.
A computation is said to be unambiguous if there exists at most one path from an initial vertex to an accepting vertex.
A cycle in the graph corresponds to an infinite loop in the computation.
The computational graph can be of infinite size if there are no restrictions on possible configurations; indeed, it is easy to see that there are Turing machines which can reach arbitrarily large configurations.
It is also possible to have finite graphs: on Deterministic finite automaton with states, for a given word of size the configuration is composed of the position of the head and the current state. So the graph is of size , and the accessible part from the initial state is of size .
This notion is useful because it reduces computational problems to graph reachability problems.
For example, since reachability is in NL when we can represent configurations in space which is logarithmic in the size of the input, and since the configuration of a Turing Machine in NL is indeed of logarithmic size, it follows that graph-reachability is complete for NL. [1]
In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configurations are of space which is logarithmic in the size of the input is in (L) NL. This is for example the case of finite automata and finite automata with one counter.
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 by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine.
In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function ,
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981.
In computational complexity theory, NL is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.
In computational complexity theory, L is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way.
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(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. The result solved the second LBA problem.
In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.
In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. The NL-complete languages are the most "difficult" or "expressive" problems in NL. If a deterministic algorithm exists for solving any one of the NL-complete problems in logarithmic memory space, then NL = L.
A read-only Turing machine or two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a deterministic finite automaton in computational power, and therefore can only parse a regular language.
In computational complexity theory, a certificate is a string that certifies the answer to a computation, or certifies the membership of some string in a language. A certificate is often thought of as a solution path within a verification process, which is used to check whether a problem gives the answer "Yes" or "No".
A symmetric Turing machine is a Turing machine which has a configuration graph that is undirected.
