Complexity classes that measure resources other than polynomial running time. PSPACE holds the problems solvable using a polynomial amount of memory, EXPTIME those solvable in exponential time by a deterministic machine, and BPP those a probabilistic machine can solve in polynomial time with a small, bounded chance of error. They sit above or beside P and NP in the map of what is feasible to compute.
Browse By
Space, Exponential Time and Probabilistic Classes
Filter Results3 entries
Sources
PSPACE, Wikipedia
Has Member: PSPACE, LeadQuote, Has Member: PSPACE, Lead
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.
EXPTIME, Wikipedia
Has Member: EXPTIME, LeadQuote, Has Member: EXPTIME, Lead
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.
BPP (complexity), Wikipedia
Has Member: BPP, LeadQuote, Has Member: BPP, Lead
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.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.