BPL (complexity)

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space),[1] sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time),[2] 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.

Error model

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 (1994) showed the weak derandomization result that BPL is contained in SC.[3] 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 L/poly. Saks and Zhou showed that BPL is contained in DSPACE(log3/2 n),[4] and in 2021 Hoza improved this to show BPL is contained in DSPACE .[5]

References

  1. ^ "Complexity Zoo: BPL". Archived from the original on 2012-08-05. Retrieved 2011-10-04.
  2. ^ Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M. (1989), "Two applications of inductive counting for complementation problems", SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1.1.394.1662, doi:10.1137/0218038
  3. ^ Nisan, N. (1994), "RL ⊆ SC", Computational Complexity, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing
  4. ^ Complexity theory lecture notes
  5. ^ Hoza, William (2021). "Better Pseudodistributions and Derandomization for Space-Bounded Computation".

Read other articles:

János Rózsa

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Bentuk asli dari nama pribadi ini adalah Rózsa János. Artikel ini menggunakan rangkaian nama Barat. János RózsaLahir19 Oktober 1937 (umur 86)Budapest, HungariaPekerjaanSutradara, produserTahun aktif1961–2004 János Rózsa (lahir 19 Okt...

 

National Bank Act

Primary federal legislation authorizing the creation of national banks in the US National Bank Act of 1863Long titleAn Act to provide a national currency, secured by a pledge of United States stocks, and to provide for the circulation and redemption thereof.Enacted bythe 37th United States CongressEffectiveFebruary 25, 1863CitationsStatutes at Large12 Stat. 665Legislative historyIntroduced in the SenatePassed the Senate on February 12, 1863 (23–21)Passed the House on Feb...

 

Памятники Рыбинска

Список памятников, расположенных на территории города Рыбинска Ярославской области России. Фото Год установки Название Авторы Описание Местоположение 1953 год Монумент «Мать-Волга» Скульпторы: С. Шапошников В. Малашкина Архитектор Н. Донских Один из крупнейших памятнико...

Mazmur 36

Mazmur 36Naskah Gulungan Mazmur 11Q5 di antara Naskah Laut Mati memuat salinan sejumlah besar mazmur Alkitab yang diperkirakan dibuat pada abad ke-2 SM.KitabKitab MazmurKategoriKetuvimBagian Alkitab KristenPerjanjian LamaUrutan dalamKitab Kristen19← Mazmur 35 Mazmur 37 → Mazmur 36 (disingkat Maz 36, Mzm 36 atau Mz 36; penomoran Septuaginta: Mazmur 35) adalah sebuah mazmur dalam bagian ke-1 Kitab Mazmur di Alkitab Ibrani dan Perjanjian Lama dalam Alkitab Kristen. Mazmur ini digubah...

 

محسن العيسى

محسن سليمان العيسى معلومات شخصية الميلاد 9 يوليو 1987 (العمر 36 سنة)المدينة المنورة الطول 1.64 م (5 قدم 4 1⁄2 بوصة) مركز اللعب وسط الجنسية السعودية  معلومات النادي النادي الحالي نادي محايل مسيرة الشباب سنوات فريق 2006–2008 الأنصار المسيرة الاحترافية1 سنوات فريق م. (هـ.) ...

 

Religion and LGBT people

Relationship between organized religions and LGBT people Symbols of the world's largest religions displayed on rainbow flags at the Queer Easter, Germany The relationship between religion and lesbian, gay, bisexual, and transgender (LGBT) people can vary greatly across time and place, within and between different religions and sects, and regarding different forms of homosexuality, bisexuality, non-binary, and transgender identities. More generally, the relationship between religion and sexual...

وليام دين هاولز

وليام دين هاولز وليام دين هاولز من تصوير أندرود معلومات شخصية الميلاد 1 مارس 1837(1837-03-01)مارتينز فيري، أوهايو الوفاة 11 مايو 1920 (عن عمر ناهز 83 عاماً)مانهاتن، نيويورك مكان الدفن مقبرة كامبريدج  [لغات أخرى]‏  الجنسية  الولايات المتحدة عضو في الأكاديمية الأمريكية ل...

 

Zimri (raja)

Zimri (Ibrani: זִמְרִי Zimrī layak dipuji; bahasa Latin: Zambri; bahasa Inggris: Zimri) adalah raja ke-5 Kerajaan Israel (Samaria) menurut Alkitab Ibrani. Ia membasmi seluruh keturunan raja Baesa dan Ela (1 Raja–raja 16:10–11) dan menjadi raja. Ia memerintah hanya 7 hari di Tirza.[1] Dalam masa pemerintahannya, dicatat hal-hal berikut: Kelakuannya dianggap jahat di mata TUHAN, sehingga ia mati tanpa ada keturunannya yang menggantikan menjadi raja.[2] Se...

 

西維吉尼亞州

西維珍尼亞 美國联邦州State of West Virginia 州旗州徽綽號：豪华之州地图中高亮部分为西維珍尼亞坐标：37°10'N－40°40'N, 77°40'W－82°40'W国家 美國加入聯邦1863年6月20日（第35个加入联邦）首府（最大城市）查爾斯頓政府 • 州长（英语：List of Governors of {{{Name}}}]]） • 副州长（英语：List of lieutenant governors of {{{Name}}}]]）吉姆·賈斯蒂斯（R）米奇·卡邁克爾（...

Lothar Beutel

Lothar BeutelBorn(1902-05-06)6 May 1902Leipzig, German EmpireDied16 May 1986(1986-05-16) (aged 84)Berlin-Steglitz, West GermanyAllegiance German Empire Nazi GermanyService/branchGerman Army SchutzstaffelYears of service1921–23 (Germany)1930–45 (SS)RankBrigadeführerService numberNSDAP #135,238Commands heldEinsatzgruppe IV Lothar Beutel (6 May 1902 – 16 May 1986) was a German pharmacist by profession and Schutzstaffel (SS) officer in World War II serving on behalf of ...

 

Simcoe Composite School

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Simcoe Composite School – news · newspapers · books · scholar · JSTOR (December 2018) (Learn how and when to remove this message) Public high school in Simcoe, Ontario, CanadaSimcoe Composite SchoolAddress40 Wilson AvenueSimcoe, Ontario, N3Y 2E5CanadaCoordinate...

 

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

 

Nydia Westman

Nydia WestmanLahirNydia Eileen Westman(1902-02-19)19 Februari 1902New York City, A.S.Meninggal23 Mei 1970(1970-05-23) (umur 68)Burbank, California, A.S.MakamOakwood Memorial Park Cemetery di Chatsworth, CaliforniaTahun aktif1932–1970Suami/istriRobert Sparks (1930–1937) (cerai) 1 anakAnakKate Williamson Nydia Eileen Westman (19 Februari 1902 – 23 Mei 1970) adalah seorang aktris dan penyanyi Amerika di panggung, layar, dan televisi. Orang tua Westman, Theodore dan...

 

محمود حسن (لاعب كرة قدم)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مايو 2023)   لمعانٍ أخرى، طالع محمود حسن (توضيح). محمود حسن معلومات شخصية الميلاد سنة 1943 (العمر 80–81 سنة)  مصر...

Daniel H. Lownsdale

American politician Daniel H. LownsdaleDaniel LownsdaleLegislator in the Provisional Government of OregonIn office1846–1846ConstituencyTuality District Personal detailsBorn1803 (1803)Died1862 (aged 58–59)OregonResting placeLone Fir Cemetery, Portland, OROccupationLegislator, tanner Daniel Lownsdale (1803–1862) was one of the founders of Portland, Oregon, United States. Coming from Kentucky sometime before 1845, Lownsdale established the first tannery near the current locat...

 

Electoral district of Fuller

Former state electoral district of New South Wales, Australia Fuller was an electoral district of the Legislative Assembly in the Australian state of New South Wales, created in 1968 in the Ryde area and named after George Fuller, Premier of New South Wales, 1922–1925. It was abolished in 1981 and largely replaced by Gladesville.[1][2][3][4] Members for Fuller Member Party Period   Peter Coleman Liberal 1968–1978   Rodney Cavalier Labor 1978–198...

 

Banking in Bhutan

Banking in Bhutan, a small country in East Asia, is an industry that has grown slowly as the country has pursued modernization. The country has a vibrant informal culture of finance which only weakly integrates formal financial services. Since its establishment in 1982, the Royal Monetary Authority of Bhutan, headquartered in Thimphu, has served as the central bank of Bhutan. The authority is responsible for issuing currency, implementing monetary policy, coordinating financial institution ac...

إبراهيم عبد المجيد

إبراهيم عبد المجيد معلومات شخصية اسم الولادة إبراهيم عبد القوي عبد المجيد خليل الميلاد 2 ديسمبر 1946 (العمر 77 سنة)الإسكندرية، مصر مواطنة مصر  الحياة العملية المدرسة الأم جامعة الإسكندرية  المهنة كاتب،  وروائي  اللغات العربية  أعمال بارزة لا أحد ينام في الإسكندر�...

 

Édouard Jacques

Pour les articles homonymes, voir Jacques. Édouard JacquesFonctionDéputé françaisBiographieNaissance 26 septembre 1828Saint-OmerDécès 14 juin 1900 (à 71 ans)14e arrondissement de ParisSépulture Cimetière du MontparnasseNationalité françaiseActivité Homme politiqueAutres informationsDistinction Chevalier de la Légion d'honneur‎Vue de la sépulture.modifier - modifier le code - modifier Wikidata Édouard Jacques est un homme politique français, né le 26 septembre 182...