BPL (complexity)

BPL (complexity)

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), [ [http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bpl Complexity Zoo: BPL] ] sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), [A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578. 1989.] is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.

The probabilistic Turing machines in the definition of BPL may only accept or reject incorrectly less than 1/3 of the time; this is called "two-sided error". The constant 1/3 is arbitrary; any "x" with 0 ≤ "x" < 1/2 would suffice. This error can be made 2−"p"("x") times smaller for any polynomial "p"("x") without using more than polynomial time or logarithmic space by running the algorithm repeatedly.

Since two-sided error is more general than one-sided error, RL and its complement co-RL are contained in BPL. BPL is also contained in PL, which is similar except that the error bound is 1/2, instead of a constant less than 1/2; like the class PP, the class PL is less practical because it may require a large number of rounds to reduce the error probability to a small constant.

Nisan showed in 1992 the weak derandomization result that BPL is contained in SC [N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.] , the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, given "polylogarithmic" space, a deterministic machine can simulate "logarithmic" space probabilistic algorithms.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • BPL — may mean:* Bank Pool Loan, a type of loan. * Barclays Premier League, professional league competition for football (soccer) clubs in England. * Broadband over Power Lines, the use of electrical power lines for telecommunications * BPL group, an… …   Wikipedia

  • RL (complexity) — In computational complexity theory, RL (Randomized Logarithmic space),[1] sometimes called RLP (Randomized Logarithmic space Polynomial time),[2] is the complexity class of problems solvable in logarithmic space and polynomial time with… …   Wikipedia

  • SC (complexity) — In computational complexity theory, SC (Steve s Class, named after Stephen Cook) [ [http://qwiki.stanford.edu/wiki/Complexity Zoo:S#sc Complexity Zoo: SC] ] is the complexity class of problems solvable by a deterministic Turing machine in… …   Wikipedia

  • Democratic peace theory — (or liberal democratic theory[1] or simply the democratic peace ) is the theory that democracies, for some appropriate definition of democracy, rarely, or even never, go to war with one another. Some have preferred the term inter democracy… …   Wikipedia

  • Newton Howard — Dr. Newton Howard is the founder and chairman of the Center for Advanced Defense Studies, a Washington, D.C. National Security Group. He is a leading international researcher on the physics of cognition (PoC) and its applications to defense and… …   Wikipedia

  • In-place algorithm — In place redirects here. For execute in place file systems, see execute in place. In computer science, an in place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of… …   Wikipedia

  • Smart grid — Public infrastructure …   Wikipedia

  • Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Dyslexia — This article is about developmental dyslexia. For acquired dyslexia, see Alexia (acquired dyslexia). Dyslexia Classification and external resources ICD 10 R48.0 ICD 9 …   Wikipedia

  • Rush (band) — Infobox musical artist Name = Rush Img capt = Alex Lifeson, Geddy Lee, and Neil Peart of Rush 30th Anniversary tour photo, 2004 Img size = 250 Landscape = yes Background = group or band Years active = 1968–present Origin = Toronto, Ontario,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”