Кіріспе
Компьютерлік ғылымдағы ұғым
Күрделілік теориясында ZPP (нөлдік қателік ықтималдық полиномиялық уақыт) – бұл ықтималдық Тьюринг машинасы бар мәселелердің күрделілік класы:
Ол әрқашан дұрыс «ИӘ» немесе «ЖОҚ» жауабын береді. Орындалу уақыты әрбір кіріс үшін күтілетін мәнде полиномиалды. Басқаша айтқанда, егер алгоритмге жұмыс істеп тұрғанда толығымен кездейсоқ монетаны лақтыруға рұқсат берілсе, ол әрқашан дұрыс жауап береді және n өлшемді мәселе үшін, орташа орындалу уақыты p(n)-нан кем болады, тіпті кейде ол әлдеқайда ұзаққа созылуы мүмкін. Мұндай алгоритм Лас-Вегас алгоритмі деп аталады. Балама ретінде, ZPP мына қасиеттері бар ықтималдық Тьюринг машинасы бар мәселелер класы ретінде анықталады:
Ол әрқашан полиномиалдық уақытта жұмыс істейді. Ол «ИӘ», «ЖОҚ» немесе «БЕЛГІСІЗ» жауабын қайтарады. Жауап әрқашан «БЕЛГІСІЗ» немесе дұрыс жауап болады. Ол әрбір кіріс үшін ең көп дегенде 1/2 ықтималдығымен «БЕЛГІСІЗ» жауабын қайтарады (ал қалған жағдайда дұрыс жауап). Бұл екі анықтама эквивалентті. ZPP анықтамасы ықтималдық Тьюринг машиналарына негізделген, бірақ түсініктілік үшін, оларға негізделген басқа күрделілік кластарына BPP және RP жатады. BQP класы басқа кездейсоқ машинаға негізделген: кванттық компьютер.
It always runs in polynomial time. It returns an answer YES, NO or DO NOT KNOW. The answer is always either DO NOT KNOW or the correct answer. It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise). The two definitions are equivalent. The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.
Тоғысу анықтамасы
ZPP класы RP және co RP кластарының қиылысына дәл тең. Бұл көбінесе ZPP-нің анықтамасы ретінде қабылданады. Мұны көрсету үшін, ең алдымен RP және co RP кластарында болатын кез келген мәселенің Лас-Вегас алгоритмі бар екенін ескерейік: Бізде RP алгоритмі A және (мүмкін толығымен басқа) co RP алгоритмі B арқылы танылған L тілі бар деп есептейік. Кірісті беріп, A алгоритмін бір қадамға орыңыз. Егер ол "ИӘ" деп қайтарса, жауап міндетті түрде "ИӘ" болуы керек. Әйтпесе, кірісті B алгоритмімен бір қадамға орыңыз. Егер ол "ЖОҚ" деп қайтарса, жауап міндетті түрде "ЖОҚ" болуы керек. Егер ешқайсысы орындалмаса, осы қадамды қайталаңыз. Бір ғана машина ғана қате жауап бере алатынын ескеріңіз, және әрбір қайталауда сол машинаның қате жауап беру ықтималдығы ең көп дегенде 50% құрайды. Бұл k-шы айналымда k-ға жету мүмкіндігі экспоненциалды түрде төмендейді дегенді білдіреді, яғни күтілетін орындалу уақыты полиномдық екенін көрсетеді. Осыдан RP ∩ co RP ZPP класына кіреді деген қорытынды шығады. ZPP класы RP ∩ co RP класына кіреді екенін көрсету үшін, егер бізде мәселені шешуге арналған Лас-Вегас алгоритмі C болса, келесі RP алгоритмін құрастыра аламыз: C алгоритмін күтілетін орындалу уақытынан кем дегенде екі есеге дейін орыңыз. Егер ол жауап берсе, сол жауапты беріңіз. Егер біз оны тоқтатқанға дейін жауап бермесе, "ЖОҚ" деп жауап беріңіз. Марков теңсіздігіне сәйкес, оны тоқтатқанға дейін жауап беру ықтималдығы кем дегенде 1/2 болады. Бұл "ИӘ" жауабы бар жағдайда, тоқтатып "ЖОҚ" деп жауап беру ықтималдығы ең көп дегенде 1/2 екенін білдіреді, бұл RP алгоритмінің анықтамасына сәйкес келеді. co RP алгоритмі бірдей, бірақ егер C алгоритмі "уақыты бітіп қалса", ол "ИӘ" деп жауап береді.
Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co RP algorithm B. Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step. Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co RP is contained in ZPP. To show that ZPP is contained in RP intersect co RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:
Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. By Markov's Inequality, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co RP algorithm is identical, except that it gives YES if C "times out".
Күрделілік теориясының қасиеттері
ZPP толықтыру бойынша жабық екені белгілі; яғни ZPP = co ZPP. ZPP өзіне қарағанда төмен, яғни ZPP мәселелерін дереу шеше алатын ZPP машинасы (ZPP оракул машинасы) қосымша мүмкіндіксіз машинадан артық қуатқа ие емес. Символдармен ZPPZPP = ZPP. ZPPNPBPP = ZPPNP. NPBPP, ZPPNP-нің ішінде орналасқан.
Басқа сыныптарға қосылу
ZPP = RP ∩ coRP болғандықтан, ZPP RP және coRP кластарының ішінде орналасқаны анық. P класы ZPP класының ішінде, ал кейбір компьютерлік ғалымдар P = ZPP деп болжайды, яғни әрбір Лас-Вегас алгоритмінің детерминистік полиномдық уақытта теңдес алгоритмі бар. ZPP = EXPTIME болатын оракул бар. ZPP = EXPTIME екенін дәлелдеу P ≠ ZPP екенін көрсетер еді, себебі P ≠ EXPTIME (уақыт иерархиясы теоремасын қараңыз).