Кіріспе

Компьютерлік ғылымдағы түсінік
Есептеу күрделілігі теориясында, компьютерлік ғылымның бір саласы, шектелген қателік ықтималдық полиномиялық уақыт (BPP) – бұл барлық мысалдар үшін 1/3-тен артық емес қателік ықтималдығымен полиномиялық уақытта шешілетін, ықтималдық Тьюринг машинасымен шешілетін шешім проблемаларының класы. BPP – бұл ең ірі практикалық проблемалар кластарының бірі, яғни BPP-дегі көптеген қызығушылық тудыратын проблемалар нақты заманауи машиналарда жылдам орындалатын тиімді ықтималдық алгоритмдерге ие. BPP детерминистік машинамен полиномиялық уақытта шешілетін проблемалар класы P-ні де қамтиды, өйткені детерминистік машина – ықтималдық машинаның ерекше жағдайы. BPP алгоритмі (1 рет орындалғанда) ≥ 2/3 ≤ 1/3 ≤ 1/3 ≥ 2/3 BPP алгоритмі (k рет орындалғанда) > 1 − 2−ck < 2−ck < 2−ck > 1 − 2−ck кейбір тұрақты c > 0 үшін.

Бейресми айтқанда, егер проблема үшін мынадай қасиеттері бар алгоритм болса, онда ол BPP класына жатады:
Ол монета лақтыруға және кездейсоқ шешімдер қабылдауға рұқсат етіледі.
Ол полиномиялық уақытта жұмыс істеуі кепілдендіріледі.
Алгоритмнің кез келген орындалуында, жауап ИӘ немесе ЖОҚ болсын, дұрыс емес жауап беру ықтималдығы 1/3-тен аспайды.

Қиындықтар

P-дегі барлық мәселелер BPP-де де болады. Дегенмен, көптеген мәселелер BPP-де екені белгілі, бірақ P-де екені белгісіз. Мұндай мәселелердің саны азайып келеді және P = BPP деген болжам бар. Ұзақ уақыт бойы BPP-де болғаны білінген, бірақ P-де екені дәлелденбеген ең танымал мәселелердің бірі – берілген санның жай сан екенін анықтау еді. Алайда, 2002 жылғы «PRIMES P-де» деген мақалада Маниндра Агравал және оның студенттері Нейрадж Каял мен Нитин Саксена осы мәселе үшін детерминистік полиномиалдық уақыт алгоритмін тапты, осылайша ол P класына жататынын көрсетті.

BPP-дегі (әсіресе co RP класындағы) және әлі күнге дейін P класына жататыны белгісіз мәселенің маңызды мысалы – полиномиалдық тепе-теңдік сынағы. Бұл мәселе полиномиалдың нөлдік полиномиалға тең екенін анықтауға қатысты, мұнда сіз кез келген берілген мән үшін полиномиалдың мәнін білесіз, бірақ оның коэффициенттерін білмейсіз. Басқаша айтқанда, айнымалыларға мәндер тағайындауға болады ма, сонда нөлден өзгеше полиномиал осы мәндерде есептелгенде нәтиже нөлден өзгеше болады ма? d дәрежесінен кем емес шекті жиыннан әр айнымалының мәнін біркелкі кездейсоқ таңдау арқылы шектелген қателік ықтималдығына қол жеткізу жеткілікті, мұнда d – полиномиалдың жалпы дәрежесі.

Қатынасты кластар

Егер кездейсоқтыққа қол жеткізуді BPP анықтамасынан алып тастасақ, күрделілік класы P-ні аламыз. Анықтама бойынша, егер кәдімгі Тьюринг машинасының орнына кванттық компьютерді қойсақ, BQP класын аламыз. BPP-ге постселекцияны қосу немесе есептеу жолдарының әртүрлі ұзындығына рұқсат ету BPPpath класын береді. BPPpath класы NP-ні қамтиды және оның кванттық баламасы PostBQP-да қамтылған. Монте-Карло алгоритмі – дұрыс болуы мүмкін кездейсоқ алгоритм. BPP класындағы мәселелер үшін көптамалы шектелген орындалу уақыты бар Монте-Карло алгоритмдері бар. Бұл Лас-Вегас алгоритмімен салыстырылады, ол кездейсоқ алгоритм, дұрыс жауапты шығарады немесе төмен ықтималдықпен "сәтсіз" деп шығарады. ZPP класын анықтау үшін полиномдық шектелген орындалу уақыты бар Лас-Вегас алгоритмдері қолданылады. Балама ретінде, ZPP әрқашан дұрыс жауап беретін және күтілетін полиномдық орындалу уақыты бар ықтималдық алгоритмдерді қамтиды. Бұл полиномдық уақыт алгоритмі деп айтудан әлсіз, себебі ол суперполиномдық уақытқа дейін жұмыс істей алады, бірақ өте төмен ықтималдықпен.

Күрделілік теориясының қасиеттері

BPP толықтыру бойынша жабық екені белгілі; яғни BPP = co BPP. BPP өзі үшін төмен, яғни BPP мәселелерін дереу шеше алатын BPP машинасы (BPP оракул машинасы) қосымша қуатсыз машинадан артық қуатқа ие емес. Символдармен көрсетсек, BPPBPP = BPP. BPP пен NP арасындағы қатынас белгісіз: BPP, NP-нің ішкі жиыны ма, NP, BPP-нің ішкі жиыны ма, әлде екеуі де емес пе – белгісіз. Егер NP, BPP-ге кірсе, бұл NP-толық мәселелерге практикалық шешімдер бар екенін білдіретін болғандықтан, бұл ықтимал емес деп саналады, онда NP = RP және PH ⊆ BPP. RP, BPP-нің, ал BPP, PP-нің ішкі жиыны екені белгілі. Бұл екеуінің қатаң ішкі жиын екені белгісіз, себебі P, PSPACE-тің қатаң ішкі жиыны ма екенін білмейміз. BPP полиномдық иерархияның екінші деңгейінде орналасқан, демек PH-қа кіреді. Нақтырақ айтқанда, Sipser–Lautemann теоремасы былай тұжырымдайды: Нәтижесінде, P = NP болса, онда P = BPP, себебі PH бұл жағдайда P-ге дейін қысқарады. Демек, P = BPP немесе P ≠ NP немесе екеуі де орын алуы мүмкін. Адлеман теоремасы бойынша, кез келген BPP тіліне жататын тілдің мүшелігін полиномдық өлшемді Буль тізбектерінің отбасы арқылы анықтауға болады, яғни BPP, P/poly-де орналасқан. Шындығында, осы фактіні дәлелдеудің салдары ретінде, шектелген ұзындығы бар кірістермен жұмыс істейтін әрбір BPP алгоритмін кездейсоқ биттердің белгілі бір тізбегін пайдаланып детерминистік алгоритмге түрлендіруге болады. Дегенмен, мұндай тізбекті табу қымбатқа түсуі мүмкін. Монте-Карло уақыт кластары үшін кейбір әлсіз ажырату нәтижелері дәлелденді, сондай-ақ қараңыз.

Жабылу қасиеттері

BPP класы толықтыру, біріктіру және қиылысу амалдары бойынша жабық.

Салыстырмалылық

Оракулдарға қатысты, A және B оракулдарының бар екенін білеміз, мұнда PA = BPPA және PB ≠ BPPB. Сонымен қатар, 1-ге жуық ықтималдығы бар кездейсоқ оракул үшін P = BPP және BPP, NP және co NP-нің ішінде қатаң түрде орналасқан. Тіпті BPP=EXPNP (соның салдарынан P<NP<BPP=EXP=NEXP) болатын оракул бар, оны келесідей итеративті құрастыруға болады. Белгілі бір (релятивизацияланған) ENP-толық мәселе үшін, оракул, егер оған мәселенің мысалынан кейін kn ұзындығындағы (n – мысалдың ұзындығы; k – тиісті кіші тұрақты) кездейсоқ тізбекпен сұрақ қойылса, жоғары ықтималдықпен дұрыс жауаптар береді. n=1-ден бастаңыз. Ұзындығы n болатын мәселенің әрбір мысалы үшін, оракул жауаптарын (төмендегі лемманы қараңыз) бекіту арқылы мысалдың нәтижесін анықтаңыз. Содан кейін, kn ұзындығындағы тізбектерден тұратын сұрақтарға мысалдың нәтижелерін ұсыныңыз, сосын ұзындығы ≤(k+1)n сұрақтардың нәтижесін белгілі деп есептеп, n+1 ұзындығындағы мысалдармен жұмысты жалғастырыңыз. Лемма: Релятивизацияланған ENP-дегі мәселені (нақтырақ айтқанда, оракул машинасының кодын және уақыт шектеуін) ескере отырып, әрбір жартылай құрастырылған оракул мен n ұзындығындағы кіріс үшін, шығысты 2O(n) оракул жауабын белгілеу арқылы анықтауға болады. Дәлел: Машина симуляцияланады, ал әлі бекітілмеген оракул жауаптары қадам сайын бекітіледі. Детерминистік есептеу қадамында ең көп дегенде бір оракул сұрауы болады. Релятивизацияланған NP оракулы үшін, мүмкін болса, есептеу жолын таңдап, базалық оракулдың жауаптарын бекіту арқылы шығысты «иә» деп белгілеңіз; әйтпесе бекіту қажет емес, және кез келген жағдайда әр қадамда базалық оракулдың ең көп дегенде 1 жауабы болады. 2O(n) қадам болғандықтан, лемма осыдан шығады. Лемма (жеткілікті үлкен k үшін) салыстырмалы ENP жауаптарына жеткілікті тізбектерді қалдыра отырып, құрылысты жасауға болатынын қамтамасыз етеді. Сонымен қатар, салыстырмалы ENP үшін сызықтық уақыт жеткілікті екенін қамтамасыз ете аламыз, тіпті функциялық мәселелер үшін де (егер функциялық оракул және сызықтық шығыс өлшемі берілген болса), және экспоненциалды түрде кішкентай (сызықтық көрсеткіші бар) қателік ықтималдығымен. Бұл құрылым тиімді, себебі кез келген оракул A берілгенде, оракул B-ні PA≤PB және EXPNPA=EXPNPB=BPPB болатындай етіп ұйымдастыруға болады. Сонымен қатар, ZPP=EXP оракулы үшін (соның салдарынан ZPP=BPP=EXP<NEXP), релятивизацияланған E есептеуіндегі жауаптарды ерекше жауапсыз жағдайға бекітуге болады, осылайша жалған жауаптар берілмейтініне көз жеткізеді.