[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bpp-zlozonosc-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bpp-zlozonosc-wikipedia\/","headline":"BPP (z\u0142o\u017cono\u015b\u0107) – Wikipedia","name":"BPP (z\u0142o\u017cono\u015b\u0107) – Wikipedia","description":"before-content-x4 W teorii z\u0142o\u017cono\u015bci obliczeniowej, BPP ( Ograniczony problem probabilistyczny wielomianowy , \u201eProbabilistyczny czas wielomianowy z ograniczonym b\u0142\u0119dem\u201d) to klasa","datePublished":"2022-03-09","dateModified":"2022-03-09","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/d\/d2\/Randomized_Complexity_Classes.svg\/220px-Randomized_Complexity_Classes.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/d\/d2\/Randomized_Complexity_Classes.svg\/220px-Randomized_Complexity_Classes.svg.png","height":"155","width":"220"},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bpp-zlozonosc-wikipedia\/","wordCount":3329,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4W teorii z\u0142o\u017cono\u015bci obliczeniowej, BPP ( Ograniczony problem probabilistyczny wielomianowy , \u201eProbabilistyczny czas wielomianowy z ograniczonym b\u0142\u0119dem\u201d) to klasa z\u0142o\u017cono\u015bci, do kt\u00f3rej nale\u017c\u0105 te problemy decyzyjne, kt\u00f3re wymagaj\u0105 czasu wielomianowego, aby mie\u0107 prawid\u0142owe rozwi\u0105zanie probabilistyczne. M\u00f3wi\u0105c dok\u0142adniej, mo\u017cna je rozwi\u0105za\u0107 w czasie wielomianowym przez probabilistyczn\u0105 maszyn\u0119 Turinga, z prawdopodobie\u0144stwem b\u0142\u0119du do maksymalnie 1\/3 dla wszystkich instancji. Algorytm BPP (1 wykonanie)  Wyprodukowana odpowied\u017a Odpowied\u017a prawid\u0142owy TAK NIE TAK \u2265 2\/3 \u2264 1\/3 NIE \u2264 1\/3 \u2265 2\/3 Algorytmo BPP ( k wykonania)  Wyprodukowana odpowied\u017a Odpowied\u017a prawid\u0142owy TAK NIE TAK > 1 – 2 – ck  0        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Nieformalnie problem dotyczy BPP, je\u015bli istnieje algorytm, kt\u00f3ry ma nast\u0119puj\u0105ce w\u0142a\u015bciwo\u015bci: Monety s\u0105 dozwolone i podejmuj\u0105 losowe decyzje Gwarantuje, \u017ce jest wykonywany w czasie wielomianowym W dowolnym dniu wykonania algorytmu ma bardziej prawdopodobne 1\/3 prawdopodobie\u0144stwa udzielenia niew\u0142a\u015bciwej odpowiedzi, czy odpowied\u017a jest tak, czy nie. BPP ma najwi\u0119ksze \u201epraktyczne\u201d klasy problem\u00f3w, tj. Wi\u0119kszo\u015b\u0107 problem\u00f3w zainteresowania BP ma wydajne algorytmy probabilistyczne, kt\u00f3re mo\u017cna wykona\u0107 na prawdziwych nowoczesnych maszynach. Z tego powodu jest to bardzo praktyczne zainteresowanie, kt\u00f3re problemy i klasy problemy znajduj\u0105 si\u0119 w BPP. BPP zawiera r\u00f3wnie\u017c P, klas\u0119 problem\u00f3w, kt\u00f3re mo\u017cna rozwi\u0105za\u0107 w czasie wielomianowym za pomoc\u0105 maszyny deterministycznej, poniewa\u017c maszyna deterministyczna jest szczeg\u00f3lnym przypadkiem maszyny probabilistycznej. W praktyce prawdopodobie\u0144stwo b\u0142\u0119du 1\/3 mo\u017ce nie by\u0107 akceptowalne, jednak wyb\u00f3r 1\/3 w definicji jest arbitralny. Mo\u017ce to by\u0107 dowolna sta\u0142a mi\u0119dzy 0 a 1\/2 (wy\u0142\u0105czna), a zestaw BPP nie b\u0119dzie si\u0119 zmieni\u0142. Nie mo\u017ce by\u0107 nawet sta\u0142e: definiuje si\u0119 t\u0119 sam\u0105 klas\u0119 problem\u00f3w, umo\u017cliwiaj\u0105c wysoki b\u0142\u0105d do 1\/2 – N – C Z jednej strony lub wymaganie niewielkiego b\u0142\u0119du do 2 – N C z drugiej strony, gdzie C To ka\u017cda pozytywna sta\u0142a, ed N Jest to d\u0142ugo\u015b\u0107 Aput. Chodzi o to, \u017ce istnieje prawdopodobie\u0144stwo b\u0142\u0119du, ale je\u015bli algorytm jest wykonywany wiele razy, mo\u017cliwo\u015b\u0107, \u017ce wi\u0119kszo\u015b\u0107 egzekucji jest b\u0142\u0119dna wyk\u0142adniczo w wyniku ograniczenia Chernoffa. [Pierwszy] Umo\u017cliwia to stworzenie niezwykle dok\u0142adnego algorytmu, po prostu wykonuj\u0105c algorytm kilka razy i przyjmuj\u0105c \u201ewi\u0119kszo\u015b\u0107 g\u0142os\u00f3w\u201d odpowiedzi. Na przyk\u0142ad, je\u015bli klasa zosta\u0142a zdefiniowana z ograniczeniem, \u017ce algorytm mo\u017ce by\u0107 b\u0142\u0119dny z maksymalnie 1\/2 100 , spowodowa\u0142oby to t\u0119 sam\u0105 klas\u0119 problem\u00f3w.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4J\u0119zyk L Jest w BPP, je\u015bli i tylko wtedy, gdy istnieje probabilistyczna maszyna Turinga M , takie M Dzia\u0142a przez czas wielomianowy na wszystkich wej\u015bciach Dla wszystkich X W L W M emituje 1 z prawdopodobie\u0144stwem wi\u0119kszym lub r\u00f3wnym 2\/3 Dla wszystkich X nie w L W M emituje 1 z prawdopodobie\u0144stwem mniejszym lub r\u00f3wnym 1\/3 W przeciwie\u0144stwie do klasy z\u0142o\u017cono\u015bci ZPP, maszyna jest wymagana M Funkcje czasu wielomianowego na wszystkich wej\u015bciach, niezale\u017cnie od wyniku losowych premier monet. Alternatywnie BPP mo\u017cna zdefiniowa\u0107 przy u\u017cyciu tylko deterministycznych maszyn Turinga. J\u0119zyk L Jest w BPP, je\u015bli i tylko wtedy, gdy jest czas wielomianowy P i maszyna deterministyczna Turinga M , takie M Dzia\u0142a przez czas wielomianowy na wszystkich wej\u015bciach Dla wszystkich X W L , wioska sznurk\u00f3w I d\u0142ugo\u015bci P (| X |) To satysfakcjonuje M (x, y) = 1 jest wi\u0119kszy lub r\u00f3wny 2\/3 Dla wszystkich X nie w L , wioska sznurk\u00f3w I d\u0142ugo\u015bci P (| X |) To satysfakcjonuje M (x, y) = 1 i mniej lub r\u00f3wne 1\/3 W tej definicji ci\u0105g I Odpowiada to wyniku losowych uruchomie\u0144 monet, kt\u00f3re zrobi\u0142by probabilistyczna maszyna Turinga. W przypadku niekt\u00f3rych aplikacji ta definicja jest preferowana, poniewa\u017c nie wspomina o probabilistycznych maszynach Turinga.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Opr\u00f3cz problem\u00f3w w P, kt\u00f3re s\u0105 oczywi\u015bcie w BP, wiele problem\u00f3w znano w BP, ale nie w P. liczba tych problem\u00f3w maleje, a przypuszczenie p = BPP. Przez d\u0142ugi czas jednym z najs\u0142ynniejszych problem\u00f3w, o kt\u00f3rych wiadomo, \u017ce znajdowa\u0142y si\u0119 w BP, ale nie bycie w P by\u0142 problem ustalenia, czy liczba jest pierwsza. Jednak w eseju z 2002 roku Program jest w P. , Manindra Agrawal i jej studenci Neeraj Kayal i Nitin Saxena znale\u017ali deterministyczny algorytm czasu na ten problem, co pokazuje, \u017ce jest on w P. Wa\u017cnym przyk\u0142adem problemu w BPP (faktycznie w CO-RP), kt\u00f3ry nie jest jeszcze znany w P, jest weryfikacja to\u017csamo\u015bci wielomaru, problem ustalenia, czy wielomian jest identyczny r\u00f3wny zerowej wielomianowi. Innymi s\u0142owy, czy istnieje przypisanie zmiennych, tak \u017ce po obliczaniu wielomianu, czy wynik jest inny od zera? Wystarczy wybra\u0107 warto\u015b\u0107 ka\u017cdej zmiennej losowo losowo przez przynajmniej podsetek D warto\u015bci w celu uzyskania krzes\u0142a o b\u0142\u0119dach wi\u0105zania, gdzie D Jest to ca\u0142kowity stopie\u0144 wielomianu. [2] Je\u015bli usuniesz dost\u0119p do losowo\u015bci z definicji BPP, otrzymujemy klas\u0119 z\u0142o\u017cono\u015bci P. Przy zdefiniowaniu klasy, je\u015bli zast\u0105pimy wsp\u00f3ln\u0105 maszyn\u0119 Turing komputerem kwantowym, otrzymujemy klas\u0119 BQP. Dodaj post -sekund\u0119 do BPP lub pozw\u00f3l, aby trasy obliczeniowe maj\u0105 r\u00f3\u017cne d\u0142ugo\u015bci, podaj klas\u0119 BPP \u015bcie\u017cka . [3] Wiadomo, \u017ce BPP \u015bcie\u017cka Zawiera NP i jest zawarty w swoim odpowiedniku kwantowym poBQP. Algorytm Monte Carlo jest losowym algorytmem, kt\u00f3ry jest prawdopodobny, jest poprawny. Problemy w klasie BPP maj\u0105 algorytmy Monte Carlo z powi\u0105zanym wielomianowym czasem wykonania. Jest to konfrontowane z algorytmem Las Vegas, kt\u00f3ry jest randomizowanym algorytmem, kt\u00f3ry emituje prawid\u0142ow\u0105 odpowied\u017a lub emituje \u201ebankructwo\u201d z niskim prawdopodobie\u0144stwem. Algorytmy Las Vegas z czasami wykonania z ograniczeniem wielomianowym s\u0105 u\u017cywane do zdefiniowania klasy ZPP. Alternatywnie, ZPP zawiera algorytmy probabilistyczne, kt\u00f3re s\u0105 zawsze prawid\u0142owe i maj\u0105 oczekiwany czas wykonywania wielomianowego. Jest to s\u0142absze ni\u017c powiedzenie, \u017ce jest to algorytm w czasie wielomianowym, poniewa\u017c mo\u017ce dzia\u0142a\u0107 przez czas wielomianowy, ale z bardzo niskim prawdopodobie\u0144stwem. BPP w odniesieniu do innych klas z\u0142o\u017cono\u015bci probabilistycznej Wiadomo, \u017ce BPP jest zamkni\u0119ty pod komplementem; To znaczy, BPP = Co-CPP. BPP sam w sobie jest niski, co oznacza, \u017ce \u200b\u200bmaszyna BPP o mocy do natychmiastowego rozwi\u0105zywania problem\u00f3w BPP (maszyna Oracle BPP) nie jest mocniejsza ni\u017c maszyna bez tej dodatkowej mocy. W symboli, BPP BPP = BPP. Zwi\u0105zek mi\u0119dzy BPP i NP jest nieznany: nie wiadomo, czy BPP jest podzbiorem NP, NP jest podzbiorem BPP lub je\u015bli s\u0105 niepor\u00f3wnywalne. Je\u015bli NP jest zawarty w BPP, co jest uwa\u017cane za ma\u0142o prawdopodobne, poniewa\u017c oznacza\u0142oby to praktyczne rozwi\u0105zania problem\u00f3w NP, w\u00f3wczas NP = RP i PH \u2286 BPP. [4] Wiadomo, \u017ce RP jest podzbiorem BPP, a BPP jest podzbiorem PP. Nie wiadomo, czy te dwa s\u0105 dwoma w\u0105skimi podzbiorami, poniewa\u017c nawet nie wiemy, czy P jest w\u0105skim podzbiorem Pspace. BPP jest zawarty na drugim poziomie hierarchii wielomianowej i dlatego jest zawarty w pH. M\u00f3wi\u0105c dok\u0142adniej twierdzenie Sipsser-Lauonmann  B P P \u2286 A 2 \u2229 Liczba Pi 2 {DisplayStyle Bppsubseteq Sigma _ {2} cap pi _ {2}} . W rezultacie p = NP prowadzi do p = bpp, poniewa\u017c pH zapada si\u0119 do p w tym przypadku. Zatem o p = bpp lub p \u260e np lub oba. Twierdzenie Adlemana stwierdza, \u017ce \u200b\u200bprzynale\u017cno\u015b\u0107 do dowolnego j\u0119zyka w BPP mo\u017ce by\u0107 okre\u015blona przez rodzin\u0119 obwod\u00f3w logicznych o wielko\u015bci wielomianowej, co oznacza, \u017ce \u200b\u200bBPP jest zawarty w P\/Pol. [5] W rzeczywisto\u015bci, w wyniku demonstracji tego faktu, ka\u017cdy algorytm BPP, kt\u00f3ry dzia\u0142a przy wej\u015bciu do przychod\u00f3w, mo\u017ce by\u0107 ob\u0142\u0105kany w algorytmie deterministycznym, kt\u00f3ry wykorzystuje sta\u0142y ci\u0105g losowych bit\u00f3w. Znalezienie tego ci\u0105gu mo\u017ce by\u0107 jednak drogie. W odniesieniu do wyroczni wiemy, \u017ce istniej\u0105 wyrogi a i b, takie, \u017ce p A = BPP A e p B \u2260 BPP B . Ponadto, w odniesieniu do losowej wyroczni z prawdopodobie\u0144stwem 1, p = BP i BPP jest \u015bci\u015ble zawarty w NP i CO-NP. [6] Istnienie niekt\u00f3rych silnych generator\u00f3w liczb losowych jest przypuszczane przez wi\u0119kszo\u015b\u0107 ekspert\u00f3w terenowych. Ta przypuszczenie oznacza, \u017ce \u200b\u200blosowo\u015b\u0107 nie daje dodatkowej mocy obliczeniowej obliczeniowej w czasie wielomianowym, to znaczy p = rp = bpp. Zauwa\u017c, \u017ce wsp\u00f3lne generatory nie wystarcz\u0105, aby pokaza\u0107 ten wynik; Ka\u017cdy algorytm probabilistyczny, \u017ce u\u017cywa typowego generatora generatora losowego, zawsze daje nieprawid\u0142owe wyniki na niekt\u00f3rych danych wej\u015bciowych niezale\u017cnie od nasienia (chocia\u017c te wej\u015bcia mog\u0105 by\u0107 rzadkie). L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan i Avi Wigderson pokazali, \u017ce je\u015bli Exptime nie upadnie do, ale BPP jest zawarty w [7] "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bpp-zlozonosc-wikipedia\/#breadcrumbitem","name":"BPP (z\u0142o\u017cono\u015b\u0107) – Wikipedia"}}]}]