翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

BPLP : ウィキペディア英語版
BPL (complexity)
In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space),〔(Complexity Zoo: BPL )〕 sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), 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.
showed the weak derandomization result that BPL is contained in SC. SC is the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, this result shows that, given ''polylogarithmic'' space, a deterministic machine can simulate ''logarithmic'' space probabilistic algorithms.
BPL is contained in NC and in DSPACE(log3/2 n) 〔(Complexity theory lecture notes )〕 and in L/poly.
== References ==


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「BPL (complexity)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.