|
NPSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''t''(''n'')) space for some function ''t'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). PSPACE is a strict superset of the set of context-sensitive languages. It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,Arora & Barak (2009) p.85 NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a non-deterministic Turing machine without needing much more space (even though it may use much more time).Arora & Barak (2009) p.86 Also, the complements of all problems in PSPACE are also in PSPACE, meaning tha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Space Hierarchy Theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space ''n'' log ''n'' than in space ''n''. The somewhat weaker analogous theorems for time are the time hierarchy theorems. The foundation for the hierarchy theorems lies in the intuition that with either more time or more space comes the ability to compute more functions (or decide more languages). The hierarchy theorems are used to demonstrate that the time and space complexity classes form a hierarchy where classes with tighter bounds contain fewer languages than those with more relaxed bounds. Here we define and prove the space hierarchy theorem. The space hierarchy theorems rely on the concept of space-constructible functions. The deterministic and nondeterminis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Space Complexity
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as O(n), O(n\log n), O(n^\alpha), O(2^n), etc., where is a characteristic of the input influencing space complexity. Space complexity classes Analogously to time complexity classes DTIME(f(n)) and NTIME(f(n)), the complexity classes DSPACE(f(n)) and NSPACE(f(n)) are the sets of languages that are decidable by deterministic (respectively, non-deterministic) Turing machines that use O(f(n)) space. The complexity classes PSPACE and NPSPACE allow f to be any polynomial, analogously to P and NP. That is, :\mathsf = \bigcup_ \mathsf(n^c) and :\mathsf = \bigcup_ \mathsf(n^c) Relationships between classes The space ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computationa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NL (complexity)
In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a generalization of L, the class for logspace problems on a deterministic Turing machine. Since any deterministic Turing machine is also a nondeterministic Turing machine, we have that L is contained in NL. NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE(log ''n''). Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of algorithms, on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science). Occasionally NL ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Savitch's Theorem
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 f\in\Omega(\log(n)), :\mathsf\left(f\left(n\right)\right) \subseteq \mathsf\left(f\left(n\right)^2\right). In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, a deterministic Turing machine can solve the same problem in the square of that space bound.Arora & Barak (2009) p.86 Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...), Savitch's theorem shows that it has a markedly more limited effect on space requ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
IP (complexity)
In computational complexity theory, the class IP (interactive polynomial time) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not relativize. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover, ''P'', which presents a proof that a given string ''n'' is a member of some language, and a verifier, ''V'', that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
QIP (complexity)
In computational complexity theory, the class QIP (which stands for Quantum Interactive Polynomial time) is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language (with high probability) and cannot convince the verifier to accept when the input is not in the language (again, with high probability). In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than 2/3, and if the input is not in the language, the verifier should be reject with probability greater than 2/3. In IP, the verifier is like a BPP machine. In QIP, the communication between the pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interactive Proof System
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct. All interactive proof systems have two requirements: * Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true. * Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transitive Closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets it is the unique minimal transitive superset of . For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". Informally, the ''transitive closure'' gives you the set of all places you can get to from any starting place. More formally, the transitive closure of a binary relation on a set is the transitive relation on set such that contains and is minimal; see . If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation. Conversely, transitive ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Second-order Logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies only variables that range over individuals (elements of the domain of discourse); second-order logic, in addition, also quantifies over relations. For example, the second-order sentence \forall P\,\forall x (Px \lor \neg Px) says that for every formula ''P'', and every individual ''x'', either ''Px'' is true or not(''Px'') is true (this is the law of excluded middle). Second-order logic also includes quantification over sets, functions, and other variables (see section below). Both first-order and second-order logic use the idea of a domain of discourse (often called simply the "domain" or the "universe"). The domain is a set over which individual elements may be quantified. Examples First-order logic can quantify over individuals, bu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
EXPSPACE
In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^) space, where p(n) is a polynomial function of n. Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in . is a strict superset of , , and and is believed to be a strict superset of . Formal definition In terms of and , :\mathsf = \bigcup_ \mathsf\left(2^\right) = \bigcup_ \mathsf\left(2^\right) Examples of problems An example of an problem is the problem of recognizing wheth ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 logic is shown to be equivalent to their computability in different types of resource-bounded models of computation. It was published in 1999 by Springer-Verlag in their book series Graduate Texts in Computer Science. Topics The book has 15 chapters, roughly grouped into five chapters on first-order logic, three on second-order logic, and seven independent chapters on advanced topics. The first two chapters provide background material in first-order logic (including first-order arithmetic, the BIT predicate, and the notion of a first-order query) and complexity theory (including formal languages, resource-bounded complexity classes, and complete problems). Chapter three begins the connection between logic and complexity, with a proof that th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> IP (complexity)")
