Table of Contents
37 relations: Alternating Turing machine, BPP (complexity), Cambridge University Press, Closed timelike curve, Co-NP, Complement (complexity), Complement (set theory), Computational complexity theory, Decision problem, Descriptive complexity theory, EXPSPACE, EXPTIME, Interactive proof system, IP (complexity), Kleene star, NL (complexity), Nondeterministic algorithm, Nondeterministic Turing machine, NP (complexity), P (complexity), P versus NP problem, P/poly, PH (complexity), Polynomial, Polynomial-time reduction, PSPACE, PSPACE-complete, QIP (complexity), Quantum computing, Savitch's theorem, Second-order logic, Space complexity, Space hierarchy theorem, Transitive closure, True quantified Boolean formula, Turing machine, Union (set theory).
Alternating Turing machine
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.
See PSPACE and Alternating Turing machine
BPP (complexity)
In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances.
See PSPACE and BPP (complexity)
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge.
See PSPACE and Cambridge University Press
Closed timelike curve
In mathematical physics, a closed timelike curve (CTC) is a world line in a Lorentzian manifold, of a material particle in spacetime, that is "closed", returning to its starting point.
See PSPACE and Closed timelike curve
Co-NP
In computational complexity theory, co-NP is a complexity class. PSPACE and co-NP are complexity classes.
See PSPACE and Co-NP
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
See PSPACE and Complement (complexity)
Complement (set theory)
In set theory, the complement of a set, often denoted by A^\complement, is the set of elements not in.
See PSPACE and Complement (set theory)
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.
See PSPACE and Computational complexity theory
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.
See PSPACE and Decision problem
Descriptive complexity theory
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.
See PSPACE and Descriptive complexity theory
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. PSPACE and EXPSPACE are complexity classes.
EXPTIME
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n. EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. PSPACE and EXPTIME are complexity classes.
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.
See PSPACE and Interactive proof system
IP (complexity)
In computational complexity theory, the class IP (interactive proof) is the class of problems solvable by an interactive proof system.
See PSPACE and IP (complexity)
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters.
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. PSPACE and nL (complexity) are complexity classes.
See PSPACE and NL (complexity)
Nondeterministic algorithm
In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.
See PSPACE and Nondeterministic algorithm
Nondeterministic Turing machine
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.
See PSPACE and Nondeterministic Turing machine
NP (complexity)
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. PSPACE and NP (complexity) are complexity classes.
See PSPACE and NP (complexity)
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. PSPACE and p (complexity) are complexity classes.
P versus NP problem
The P versus NP problem is a major unsolved problem in theoretical computer science.
See PSPACE and P versus NP problem
P/poly
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. PSPACE and P/poly are complexity classes.
PH (complexity)
In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH was first defined by Larry Stockmeyer. PSPACE and pH (complexity) are complexity classes.
See PSPACE and PH (complexity)
Polynomial
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer powers, and has a finite number of terms.
Polynomial-time reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another.
See PSPACE and Polynomial-time reduction
PSPACE
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. PSPACE and PSPACE are complexity classes.
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. PSPACE and PSPACE-complete are complexity classes.
See PSPACE and PSPACE-complete
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.
See PSPACE and QIP (complexity)
Quantum computing
A quantum computer is a computer that exploits quantum mechanical phenomena.
See PSPACE and Quantum computing
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.
See PSPACE and Savitch's theorem
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.
See PSPACE and Second-order logic
Space complexity
The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input.
See PSPACE and Space complexity
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.
See PSPACE and Space hierarchy theorem
Transitive closure
In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive.
See PSPACE and Transitive closure
True quantified Boolean formula
In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas.
See PSPACE and True quantified Boolean formula
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.
Union (set theory)
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.
See PSPACE and Union (set theory)
References
Also known as AP (complexity), APTIME, NPSPACE, P = PSPACE problem, PSPACE (complexity), PSPACE-Hard, Polynomial space.