Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік күрделілік теориясында IP (интерактивті дәлелдеу) класы – интерактивті дәлелдеу жүйесімен шешілетін мәселелер класы. Ол PSPACE класына тең. Бұл нәтиже бірнеше мақалада көрсетілді: біріншісінде Лунд, Карлофф, Фортноу және Нисан ко NP-де көптеген интерактивті дәлелдемелер бар екенін дәлелдеді; ал екіншісінде Шамир осы әдісті пайдаланып IP=PSPACE екенін көрсетті. Бұл нәтиже дәлелдеме салыстырмалы емес, кең таралған мысал. Интерактивті дәлелдеу жүйесінің түсінігін алғаш рет 1985 жылы Шафи Голдвассер, Сильвио Микали және Чарльз Рэккофф енгізді. Интерактивті дәлелдеу жүйесі екі машинадан тұрады: P дәлелдеушісі, берілген n жолының белгілі бір тілге жататындығын дәлелдейді, және V тексерушісі, ұсынылған дәлелдеменің дұрыстығын тексереді. Дәлелдеушінің есептеу және жад көлемі шексіз деп есептеледі, ал тексеруші – кездейсоқ биттер тізбегіне қол жеткізе алатын, полиномиалдық уақытта жұмыс істейтін ықтималдық машинасы, оның тізбегінің ұзындығы n-нің өлшеміне полиномиалды. Бұл екі машина p(n) полиномиалдық санындағы хабарламаларды алмасады және өзара әрекеттесу аяқталғаннан кейін тексеруші n-нің тілге жататындығын 1/3 қателік мүмкіндігімен анықтауы керек. (Осылайша, BPP-дегі кез келген тіл IP-де болады, себебі тексеруші дәлелдеушіге мән бермей, өзі шешім қабылдай алады.)
In computational complexity theory, the class IP (interactive proof) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not relativize. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)
IP = PSPACE дәлелденуі
Дәлелді екі бөлікке бөлуге болады, біз IP PSPACE-қа және PSPACE IP-ге кіретінін көрсетеміз.
The proof can be divided in two parts, we show that IP ⊆ PSPACE and PSPACE ⊆ IP.
PSPACE IP
PSPACE⊆IP екенін дәлелдеу үшін қолданылатын әдісті түсіндіру мақсатында, Лунд және авторлар дәлелдеген әлсіз теореманы бірінші кезекте дәлелдейміз: #SAT ∈ IP. Содан кейін, осы дәлелдемеден алынған ұғымдарды пайдаланып, TQBF ∈ IP екенін көрсетуге кеңейтеміз. TQBF PSPACE-ке толық болғандықтан, және TQBF ∈ IP болғандықтан, PSPACE ⊆ IP.
In order to illustrate the technique that will be used to prove PSPACE ⊆ IP, we will first prove a weaker theorem, which was proven by Lund, et al. : #SAT ∈ IP. Then using the concepts from this proof we will extend it to show that TQBF ∈ IP. Since TQBF ∈ PSPACE complete, and TQBF ∈ IP then PSPACE ⊆ IP.
Нұсқалар
Интерактивті дәлелдеу жүйесінің анықтамасын аз ғана өзгертетін бірнеше ИП нұсқалары бар. Ең танымалдарының кейбірін төменде жинақтап келтіреміз.
There are a number of variants of IP which slightly modify the definition of the interactive proof system. We summarize some of the better known ones here.
dIP
IP-дің кіші жиыны – детерминистік интерактивті дәлелдеу класы, ол IP-ге ұқсас, бірақ детерминистік тексерушіге ие (яғни, кездейсоқтық қолданбайды). Бұл класс NP-ге тең.
A subset of IP is the deterministic Interactive Proof class, which is similar to IP but has a deterministic verifier (i. e. with no randomness). This class is equal to NP.
ТМК
1988 жылы Голдвассер және авторлар IP-ге негізделген, екі тәуелсіз растаушысы бар, MIP деп аталатын одан да күшті интерактивті дәлелдеу жүйесін жасады. Тексеруші оларға хабар жіберуді бастағаннан кейін екі растаушы бір-бірімен байланыса алмайды. Егер қылмыскер мен оның серігі бөлек бөлмелерде сұраққа тартылса, оның өтірік айтып жатқанын анықтау оңай болғандай, егер басқа растаушымен тексеруге болады болса, тексерушіні алдауға тырысатын қаскөй растаушыны анықтау әлдеқайда оңай. Шындығында, бұл соншалықты пайдалы болғандықтан Бабай, Фортноу және Лунд MIP = NEXPTIME, яғни экспоненциалды уақытта нон-детерминистік машинамен шешілетін барлық мәселелер классы, өте үлкен класс екенін көрсетті. Сонымен қатар, NP класындағы барлық тілдер MIP жүйесінде қосымша болжамдарсыз нөлдік білімді дәлелдемеге ие; бұл IP үшін тек бір бағытты функциялардың бар екендігін болжайды.
In 1988, Goldwasser et al. created an even more powerful interactive proof system based on IP called MIP in which there are two independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier if there is another prover it can double check with. In fact, this is so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. Moreover, all languages in NP have zero knowledge proofs in an MIP system, without any additional assumptions; this is only known for IP assuming the existence of one way functions.
IPP
IPP (шекарасыз IP) – IP-нің бір түрі, онда BPP тексерушісі PP тексерушісімен алмастырылады. Нақтырақ айтқанда, толықтығы және дұрыстығы шарттары келесідей өзгертіледі:
IPP (unbounded IP) is a variant of IP where we replace the BPP verifier by a PP verifier. More precisely, we modify the completeness and soundness conditions as follows:
Толықтығы: Егер тізбе тілге кірсе, адал растаушы адал тексерушіні осы фактіге кем дегенде 1/2 ықтималдығымен көндіреді. Дұрыстығы: Егер тізбе тілге кірмесе, ешқандай растаушы адал тексерушіні оның тілге кіргеніне сендіре алмайды, тек 1/2-ден кем ықтималдықпен. IPP сонымен қатар PSPACE-ке тең болғанымен, IPP протоколдары оракулдарға қатысты IP-ден өте өзгеше әрекет етеді: IPP барлық оракулдарға қатысты PSPACE-ке тең, ал IP дерлік барлық оракулдарға қатысты PSPACE-ке тең емес.
Completeness: if a string is in the language, the honest verifier will be convinced of this fact by an honest prover with probability at least 1/2. Soundness: if the string is not in the language, no prover can convince the honest verifier that it is in the language, except with probability less than 1/2. Although IPP also equals PSPACE, IPP protocols behaves quite differently from IP with respect to oracles: IPP=PSPACE with respect to all oracles, while IP ≠ PSPACE with respect to almost all oracles.
QIP
QIP – IP нұсқасы, онда BPP тексерушісі BQP тексерушісімен алмастырылады, ал BQP – кванттық компьютерлердің полиномиалдық уақытта шеше алатын мәселелер класы. Хабарлар кубиттерден құралған. 2009 жылы Jain, Ji, Upadhyay және Watrous QIP-тің PSPACE-ге де тең екенін дәлелдеді, бұл өзгеріс протоколға қосымша мүмкіндік бермейтінін көрсетеді. Бұл Кітаев пен Уотрустың бұрынғы нәтижесін қамтиды, яғни QIP = QIP[3], сондықтан үш раундтан көп қажет емес.
QIP is a version of IP replacing the BPP verifier by a BQP verifier, where BQP is the class of problems solvable by quantum computers in polynomial time. The messages are composed of qubits. In 2009, Jain, Ji, Upadhyay, and Watrous proved that QIP also equals PSPACE, implying that this change gives no additional power to the protocol. This subsumes a previous result of Kitaev and Watrous that QIP is contained in EXPTIME because QIP = QIP[3], so that more than three rounds are never necessary.