Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік күрделілік теориясындағы интерактивті дәлелдеу жүйесі
Interactive proof system in computational complexity theory
Компьютерлік күрделілік теориясында Артур–Мерлин протоколы – бұл интерактивті дәлелдеу жүйесі, онда тексерушінің таңдаулары (монетаны лақтыруы) қоғамдық болып табылады (яғни, дәлелдеушіге де белгілі). Дәлелдеуші жеке таңдаулары бар кез келген ұзындығының интерактивті дәлелдемесі бар барлық (формалды) тілдер, сондай-ақ қоғамдық таңдаулары бар интерактивті дәлелдемеге ие екенін дәлелдеді. Протоколдағы екі қатысушы, тиісінше Артур және Мерлин деп аталатын болса, негізгі болжам Артурдың кездейсоқ сандарды жасайтын құрылғымен жабдықталған стандартты компьютер (немесе тексеруші) екендігі, ал Мерлин – шексіз есептеу қуатына ие оракул (сонымен қатар дәлелдеуші деп те аталады). Алайда, Мерлин міндетті түрде адал болмайды, сондықтан Артур Мерлиннің Артурдың сұрақтарына жауап ретінде ұсынған ақпаратын талдап, мәселені өзі шешуі керек. Егер жауап "иә" болса, Мерлиннің Артурдың кем дегенде 2/3 уақытында қабылдауына себеп болатын жауаптар сериясы бар болса, және егер жауап "жоқ" болса, Артур ешқашан 1/3 уақытынан артық қабылдамайтын болса, онда бұл протокол бойынша мәселені шешуге болады. Осылайша, Артур – ықтималдық полиномиалдық уақыт тексерушісі болып табылады, өйткені оған шешімдер мен сұраныстар жасау үшін полиномиалдық уақыт беріледі.
In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i. e. known to the prover too). proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. Given two participants in the protocol called Arthur and Merlin respectively, the basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover). However, Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2/3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1/3 of the time. Thus, Arthur acts as a probabilistic polynomial time verifier, assuming it is allotted polynomial time to make its decisions and queries.
Қасиеттері
MA және AM екеуі де өздеріндегі өзгерістерге қарамастан, толыққандылық талабына қатысты өзгеріс жасалса да өзгермейді, яғни Артур x тілде болғанда 1 ықтималдығымен (2/3 орнына) қабылдайды. Кез келген k ≥ 2 тұрақты үшін AM[k] класы AM[2] класына тең. Егер k енгізу көлеміне полиномиялық түрде байланысты болса, онда AM[poly(n)] класы IP класына тең, ал IP класы PSPACE класына тең және AM[2] класынан күштірек деп есептеледі. MA класы AM класының ішінде қамтылған, себебі AM[3] класы MA класын қамтиды: Артур Мерлиннің сертификатын алғаннан кейін, қажетті монеталарды лақтырып, оларды Мерлинге жіберіп, жауапты назарға алмайды. AM және MA кластарының өзгешелігі бар ма деген сұрақ ашық күйде. Ықтимал тізбек шектеулері (P=BPP дегенге ұқсас) бойынша, екеуі де NP класына тең. AM класы BP⋅NP класына тең, мұнда BP – шектелген қателікпен есептеу операторы. Сондай-ақ, (ExistsBPP деп те жазылады) MA класының ішкі жиыны болып табылады. MA класы тең бе деген сұрақ әлі де ашық. Мерлиннің Артурдың кездейсоқ шешімдерінің нәтижесін болжау мүмкін емес жеке монета протоколына ауысу, жалпы жағдайда өзара әрекеттесу раундтарының санын ең көп дегенде 2-ге арттырады. Сондықтан AM класының жеке монета нұсқасы, AM класының жалпы монета нұсқасына тең. MA класы NP және BPP кластарын қамтиды. BPP үшін бұл анық, себебі Артур Мерлинді елемеу арқылы мәселені тікелей шеше алады; ал NP үшін Мерлин Артурға тек сертификат жіберуі керек, оны Артур полиномиалдық уақытта детерминистік түрде тексеруге болады. MA және AM кластары полиномиалдық иерархияның ішінде қамтылған. Атап айтқанда, MA класы Σ2P және Π2P кластарының қиылысында, ал AM класы Π2P класының ішінде қамтылған. Одан да әрі, MA класы «симметриялық ауысу» деп аталатын күрделілік класының ішкі класы болып табылады. Бұл Сипсер–Лаутеман теоремасының жалпылауы. AM класы NP/poly класында қамтылған, бұл полиномиалдық кеңеспен полиномиалдық уақытта шешілетін шешімдік мәселелер класы. Дәлел Адлеман теоремасының вариациясы болып табылады. MA класы кванттық нұсқасы QMA класында қамтылған. AM класы екі графтың изоморфты емес екенін анықтау мәселесін қамтиды. Жеке монеталарды пайдалану протоколы келесідей және оны жалпы монеталар протоколына айналдыруға болады. G және H екі графигінен біреуін кездейсоқ таңдап, оның төбелерінің кездейсоқ орналасуын таңдап, Мерлинге I орналасқан графигін ұсынады. Мерлин I графигі G немесе H графигінен жасалған ба деп жауап беруі керек. Егер графтар изоморфты болмаса, Мерлин толыққанды сеніммен жауап бере алады (I графигі G графигіне изоморфты екенін тексеру арқылы). Алайда, егер графтар изоморфты болса, I графигін жасау үшін G немесе H графигін қолдану мүмкін, және олардың ықтималдығы бірдей. Бұл жағдайда Мерлин оларды ажырата алмайды және Артурды ең көп дегенде 1/2 ықтималдығымен сендіре алады, бұл қайталану арқылы 1/4-ке дейін арттырылуы мүмкін. Бұл, шын мәнінде, нөлдік білімді дәлелдеу. Егер AM класы coNP класын қамтитын болса, онда PH = AM. Бұл граф изоморфизмінің NP-толық емес екендігінің дәлелі, себебі бұл полиномиалдық иерархияның құлауын білдіреді. ERH шарты бойынша, кез келген d үшін «Әрқайсысы бүтін сандық коэффициенттері бар және ең көп дегенде d дәрежелі көпөлшемді полиномиалдар жиынтығы берілген болса, олардың ортақ күрделі нөлі бар ма?» мәселесі AM класында қамтылған.
Both MA and AM remain unchanged if their definitions are changed to require perfect completeness, which means that Arthur accepts with probability 1 (instead of 2/3) when x is in the language. For any constant k ≥ 2, the class AM[k] is equal to AM[2]. If k can be polynomially related to the input size, the class AM[poly(n)] is equal to the class, IP, which is known to be equal to PSPACE and is widely believed to be stronger than the class AM[2]. MA is contained in AM, since AM[3] contains MA: Arthur can, after receiving Merlin's certificate, flip the required number of coins, send them to Merlin, and ignore the response. It is open whether AM and MA are different. Under plausible circuit lower bounds (similar to those implying P=BPP), they are both equal to NP. AM is the same as the class BP⋅NP where BP denotes the bounded error probabilistic operator. Also, ( also written as ExistsBPP) is a subset of MA. Whether MA is equal to is an open question. The conversion to a private coin protocol, in which Merlin cannot predict the outcome of Arthur's random decisions, will increase the number of rounds of interaction by at most 2 in the general case. So the private coin version of AM is equal to the public coin version. MA contains both NP and BPP. For BPP this is immediate, since Arthur can simply ignore Merlin and solve the problem directly; for NP, Merlin need only send Arthur a certificate, which Arthur can validate deterministically in polynomial time. Both MA and AM are contained in the polynomial hierarchy. In particular, MA is contained in the intersection of Σ2P and Π2P and AM is contained in Π2P. Even more, MA is contained in subclass , a complexity class expressing "symmetric alternation". This is a generalization of Sipser–Lautemann theorem. AM is contained in NP/poly, the class of decision problems computable in non deterministic polynomial time with a polynomial size advice. The proof is a variation of Adleman's theorem. MA is contained in PP; this result is due to Vereshchagin. MA is contained in its quantum version, QMA. AM contains the problem of deciding if two graphs are not isomorphic. The protocol using private coins is the following and can be transformed to a public coin protocol. Given two graphs G and H, Arthur randomly chooses one of them, and chooses a random permutation of its vertices, presenting the permuted graph I to Merlin. Merlin has to answer if I was created from G or H. If the graphs are nonisomorphic, Merlin will be able to answer with full certainty (by checking if I is isomorphic to G). However, if the graphs are isomorphic, it is both possible that G or H was used to create I, and equally likely. In this case, Merlin has no way to tell them apart and can convince Arthur with probability at most 1/2, and this can be amplified to 1/4 by repetition. This is in fact a zero knowledge proof. If AM contains coNP then PH = AM. This is evidence that graph isomorphism is unlikely to be NP complete, since it implies collapse of polynomial hierarchy. It is known, assuming ERH, that for any d the problem "Given a collection of multivariate polynomials each with integer coefficients and of degree at most d, do they have a common complex zero?" is in AM.