Кіріспе
Компьютерлік күрделілік теориясында интерактивті дәлелдеу жүйесі – екі тараптың: дәлелдеуші мен тексерушінің арасындағы хабар алмасуы ретінде есептеуді модельдейтін абстрактілі машина. Тараптар белгілі бір жолдың тілге жататындығын анықтау үшін хабар алмасу арқылы өзара әрекеттеседі. Дәлелдеуші шексіз есептеу ресурстарына ие, бірақ оған сенуге болмайды, ал тексерушінің есептеу қуаты шектеулі, бірақ ол әрқашан адал деп есептеледі. Тексеруші мен дәлелдеуші арасында хабарлар жіберіледі, тексеруші мәселеге жауап бергенше және оның дұрыстығына "көз жеткізгенше". Барлық интерактивті дәлелдеу жүйелері екі талапқа бағынады:
Толықтығы: егер мәлімдеме дұрыс болса, адал дәлелдеуші (яғни, протоколды дұрыс сақтайтын) адал тексерушіні оның шындыққа сәйкес екеніне көндіре алады. Дұрыстығы: егер мәлімдеме жалған болса, ешқандай дәлелдеуші, тіпті протоколды бұзса да, адал тексерушіні оның дұрыс екеніне көндіре алмайды, тек шағын ғана ықтималдықпен. Жүйенің ерекшелігі, сонымен қатар оның тани алатын тілдердің күрделілік класы, тексерушіге қойылған шектеулерге және оған берілген мүмкіндіктерге байланысты. Мысалы, көптеген интерактивті дәлелдеу жүйелері тексерушінің кездейсоқ таңдау жасау қабілетіне тікелей байланысты. Бұл сондай-ақ алмасылатын хабарламалардың сипатына – олардың саны мен мазмұнына да байланысты. Интерактивті дәлелдеу жүйелерінің тек бір машинаны пайдалана отырып анықталған дәстүрлі күрделілік кластарына маңызды әсер ететіні анықталды. Интерактивті дәлелдеу жүйелерін сипаттайтын негізгі күрделілік кластары – AM және IP.
Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true. Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small probability. The specific nature of the system, and so the complexity class of languages it can recognize, depends on what sort of bounds are put on the verifier, as well as what abilities it is given—for example, most interactive proof systems depend critically on the verifier's ability to make random choices. It also depends on the nature of the messages exchanged—how many and what they can contain. Interactive proof systems have been found to have some important implications for traditional complexity classes defined using only one machine. The main complexity classes describing interactive proof systems are AM and IP.
Өмірбаян
Әрбір интерактивті дәлелдеу жүйесі жолдардың ресми тілін анықтайды. Дәлелдеу жүйесінің дұрыстығы – бұл ешбір дәлелдеушінің қате мәлімдеме үшін тексерушіні қабылдауға мәжбүр ете алмайтын қасиет, тек белгілі бір шағын ықтималдықпен ғана. Бұл ықтималдықтың жоғарғы шегі дәлелдеу жүйесінің қателік деңгейі деп аталады. Формалдырақ айтқанда, кез келген дәлелдеуші және кез келген үшін:
кейбір үшін. Егер қателік деңгейі тексерушінің потенциалды жұмыс уақытының полиномдық үлесімен шектелген болса (яғни), онда тексерушінің жұмыс уақытына қатысты қателік деңгейі мардымсыз функцияға дейін төмендетілгенше, дұрыстықты күшейтуге әрқашан болады. Бұл дәлелдемені қайталап, барлық дәлелдемелер тексерілген жағдайда ғана қабылдау арқылы жүзеге асырылады. қайталаудан кейін қателік деңгейі -тен -ке дейін төмендейді.
NP
NP күрделілік класын өте қарапайым дәлелдеу жүйесі ретінде қарастыруға болады. Бұл жүйеде тексеруші – детерминистік, полиномиалдық уақытта жұмыс істейтін машина (P машинасы). Протокол мынадай:
Дәлелдеуші кірісті қарастырып, шексіз мүмкіндіктерін пайдалана отырып, шешімді есептейді және полиномиалдық өлшемдегі дәлелдеу сертификатын қайтарады. Тексеруші сертификаттың детерминистік полиномиалдық уақыт ішінде дұрыс екенін тексереді. Егер сертификат дұрыс болса, қабылдайды, әйтпесе, қабылдамайды. Егер жарамды дәлелдеу сертификаты болса, дәлелдеуші осы сертификатты ұсыну арқылы тексерушіні қабылдауға әрқашан көндіре алады. Бірақ, егер жарамды дәлелдеу сертификаты болмаса, кіріс тілге жатпайды, және ешқандай дәлелдеуші, тіпті қастандық ойласа да, тексерушіні басқаша ойға көндіре алмайды, себебі кез келген дәлелдеу сертификаты қабылданбайды.
The prover looks at the input and computes the solution using its unlimited power and returns a polynomial size proof certificate. The verifier verifies that the certificate is valid in deterministic polynomial time. If it is valid, it accepts; otherwise, it rejects. In the case where a valid proof certificate exists, the prover is always able to make the verifier accept by giving it that certificate. In the case where there is no valid proof certificate, however, the input is not in the language, and no prover, however malicious it is, can convince the verifier otherwise, because any proof certificate will be rejected.
Артур Мерлин және Мерлин Артур протоколдары
NP өзара әрекеттесуді пайдалану ретінде қарастырылса да, 1985 жылға дейін өзара әрекеттесу арқылы есептеу тұжырымдамасы (кешенділік теориясы аясында) екі тәуелсіз зерттеушілер тобымен ұсынылды. Бір тәсілді, "Топтар теориясын кездейсоқтыққа сату" атты еңбегін жариялаған Ласло Бабаи, Артур-Мерлин (AM) сыныптар иерархиясын анықтады. Осы ұсынылымда Артур (тексеруші) – ықтималдық, полиномиалдық уақыт машинасы, ал Мерлин (дәлелдеуші) – шексіз ресурстарға ие. Әсіресе MA класы – жоғарыдағы NP өзара әрекеттесуінің қарапайым кеңейтілген түрі, онда тексеруші детерминистік емес, ықтималдық болып табылады. Сондай-ақ, тексерушінің әрқашан жарамды сертификаттарды қабылдап, жарамсыз сертификаттарды қабылдамауын талап етудің орнына, ол көбірек кешірімді:
Толықтығы: егер тізбе тілге жатса, дәлелдеуші тексерушінің кемінде 2/3 ықтималдығымен (тексерушінің кездейсоқ таңдауына байланысты) қабылдайтын сертификат ұсынуы керек. Дұрыстығы: егер тізбе тілге жатпаса, ешқандай дәлелдеуші, тіпті қастандықпен әрекет етсе де, тексерушіні тізбені 1/3 ықтималдан артық қабылдауға көндіре алмайды. Бұл машина қарапайым NP өзара әрекеттесу протоколынан күштірек болуы мүмкін, ал сертификаттарды тексеру оңай, себебі BPP алгоритмдері практикалық есептеулерді абстракциялайды (BPP қараңыз).
Completeness: if the string is in the language, the prover must be able to give a certificate such that the verifier will accept with probability at least 2/3 (depending on the verifier's random choices). Soundness: if the string is not in the language, no prover, however malicious, will be able to convince the verifier to accept the string with probability exceeding 1/3. This machine is potentially more powerful than an ordinary NP interaction protocol, and the certificates are no less practical to verify, since BPP algorithms are considered as abstracting practical computation (see BPP).
Қоғамдық монета протоколы мен жеке монета протоколы
Қоғамдық монета протоколында тексеруші жасаған кездейсоқ таңдаулар жария етіледі. Жеке монета протоколында олар құпия болып қалады. Бабай өзінің MA үшін дәлелдеу жүйесін анықтаған сол конференцияда Шафи Голдвассер, Сильвио Микали және Чарльз Ракофф IP[f(n)] интерактивті дәлелдеу жүйесін анықтаған мақала жариялады. Бұл MA протоколындағы сияқты машиналарды пайдаланады, бірақ n өлшемді кіріс үшін f(n) раундқа рұқсат етіледі. Әр раундта тексеруші есептеулерді орындайды және дәлелдеушіге хабарлама жібереді, ал дәлелдеуші есептеулерді орындайды және ақпаратты тексерушіге қайтарады. Соңында тексеруші шешім қабылдауы керек. Мысалы, IP[3] протоколында тізбек VPVPVPV болады, мұнда V – тексерушінің кезегі, ал P – дәлелдеушінің кезегі. Артур–Мерлин протоколдарында Бабай f(n) раундқа рұқсат беретін AM[f(n)] класын анықтады, бірақ машинаға қосымша бір талап қойды: тексеруші өзінің есептеулерінде қолданатын кездейсоқ биттерді дәлелдеушіге көрсетуі керек. Соның салдарынан тексеруші дәлелдеушіден ештеңені "жасыра алмайды", себебі дәлелдеуші тексерушінің қолданған кездейсоқ биттерін білген жағдайда, тексерушінің барлық әрекеттерін симуляциялай алады. Бұл қоғамдық монета протоколы деп аталады, өйткені кездейсоқ биттер ("монета тастау") екі машинаға да көрінеді. IP тәсілі керісінше, жеке монета протоколы деп аталады. Қоғамдық монеталардың басты мәселесі – егер дәлелдеуші тексерушіні тілге жатпайтын тізбекті қабылдауға көндіргісі келсе, тексеруші өзінің ішкі күйін жасыра алса, оның жоспарларын тоқтатуға мүмкіндігі бар сияқты. Осы себепті IP дәлелдеу жүйелерін анықтауға басты түрткі болды. 1986 жылы Голдвассер мен Сипсер, күтпегендей, тексерушінің монета тастауды дәлелдеушіден жасыру қабілетінің көп пайдасы жоқ екенін көрсетті, себебі Артур–Мерлиннің тек екі раунды қоғамдық монета протоколы барлық бірдей тілдерді тануға қабілетті. Соның нәтижесінде қоғамдық және жеке монета протоколдары шамамен теңдес. Шындығында, Бабай 1988 жылы көрсеткендей, AM[k]=AM барлық тұрақты k үшін, сондықтан IP[k] AM-ге қарағанда ешқандай артықшылыққа ие емес. Бұл кластардың күшін көрсету үшін граф изоморфизмі мәселесін қарастырайық, яғни бір графтың төбелерін басқа графқа сәйкес келтіру арқылы екі графты бірдей етуге болатынын анықтау мәселесі. Бұл мәселе NP класында, себебі дәлелдеу сертификаты – екі графты теңестіретін ауыстыру. Көрініп тұрғанындай, граф изоморфизмі мәселесінің толықтыруы, co NP мәселесі, NP класында емес, AM алгоритміне ие және оны көрудің ең жақсы жолы жеке монета алгоритмі арқылы.
complement of the graph isomorphism problem, a co NP problem not known to be in NP, has an AM algorithm and the best way to see it is via a private coins algorithm.
IP-тің атауы
Жеке монеталар көмектеспеуі мүмкін, бірақ өзара әрекеттесу раундтарының көбеюі көмектеседі. Егер ықтималдық тексеруші машинасы мен шексіз күшті дәлелдеуші полиномдық сандағы раундтар бойы өзара әрекеттесуіне мүмкіндік берсек, онда біз IP деп аталатын мәселелер класын аламыз. 1992 жылы Ади Шамир күрделілік теориясының маңызды нәтижелерінің бірінде IP класы PSPACE класына тең екенін көрсетті, PSPACE – бұл полиномдық кеңістікте қарапайым детерминистік Тьюринг машинасымен шешілетін мәселелер класы.
QIP
Егер жүйе элементтері кванттық есептеуді пайдалануға мүмкіндік берілсе, онда бұл жүйе кванттық интерактивті дәлелдеу жүйесі деп аталады, ал оған сәйкес күрделілік класы QIP деп аталады. Бірқатар зерттеулердің нәтижесінде 2010 жылы QIP = PSPACE екендігі анықталды.
Білімі жоқ
Интерактивті дәлелдеу жүйелері NP-ге жатпайтын проблемаларды шеше алады, бірақ бір бағытты функциялардың бар екендігі туралы болжамдар бойынша, дәлелдеуші шешім туралы ешқандай ақпарат бермей, тексерушіге шешімнің дұрыстығына көндіре алады. Бұл тексерушіге толық шешімді сенуге болмайтын жағдайларда маңызды. Алғашқыда, тексеруші куәліксіз шешімге сенуі мүмкін емес сияқты көрінеді, бірақ мұндай дәлелдемелер, нөлдік білім дәлелдемелері деп аталады, NP-дегі барлық проблемалар үшін бар деп саналады және криптографияда құнды. Нөлдік білімді дәлелдеу алғаш рет Голдвассер, Микали және Ракоффтың 1985 жылғы интерактивті дәлелдеу туралы түпнұсқалық мақаласында нақты сандық теориялық тілдер үшін айтылған. Олардың мүмкіндіктерінің шегін Одед Голдрейх, Сильвио Микали және Ави Вигдерсон көрсетті.
ТМК
IP-ді жасаушылардың бір мақсаты – ең қуатты интерактивті дәлелдеу жүйесін құру болды. Бастапқыда, оны күшейту текшерушінің күшін арттыру арқылы ғана мүмкін көрінеді, бірақ бұл оны практикалық емес етеді. Голдвассер және тағы басқалар 1988 жылы жариялаған «Көп дәлелдеуші интерактивті дәлелдеулер: қалай шешілмейтін болжамдарды жоюға болады» деген мақаласында МИП деп аталатын IP-нің екі тәуелсіз дәлелдеушісі бар түрін анықтады. Тексеруші оларға хабар жіберуді бастағаннан кейін екі дәлелдеуші бір-бірімен байланыса алмайды. Қылмыскер мен оның серігі бөлек бөлмелерде тексерілгенде, қылмыскердің жалған айтқанын анықтау оңай болатындай, басқа дәлелдеушінің болуы тілге жатпайтын мәліметтерді қабылдауға тырысатын қасақана дәлелдеушіні анықтауды әлдеқайда жеңілдетеді. Шындығында, бұл соншалықты пайдалы, сондықтан Бабай, Фортноу және Лунд МИП = NEXPTIME екенін көрсетті, яғни бұл экспоненциалды уақытта нон-детерминистік машинамен шешілетін барлық мәселелердің класы, және ол өте кең класс. NEXPTIME құрамында PSPACE бар, және оның PSPACE-ден әлдеқайда үлкен екеніне сенімді. Екіден артық қосымша дәлелдеушілерді қосу тілдерді тану қабілетін арттырмайды. Бұл нәтиже белгілі PCP теоремасының «төмендетілген» нұсқасы деп есептелетін жол ашты. MIP сонымен қатар NP-дегі әрбір тіл үшін нөлдік білімді дәлелдеуді IP-нің талап ететін бір бағытты функцияларға тәуелділіксіз сипаттауға мүмкіндік беретін пайдалы қасиетке ие. Бұл бұзылуы мүмкін емес криптографиялық алгоритмдерді жобалауға әсер етеді.
PCP
ИС-ті жобалаушылар Бабайдың интерактивті дәлелдеу жүйелерінің жалпылануын қарастырғанда, басқалары шектеулерді қарастырды. Өте пайдалы интерактивті дәлелдеу жүйесі – PCP(f(n), g(n)), бұл MA-ның шектеуі, онда Артур тек f(n) кездейсоқ битті пайдалана алады және Мерлин жіберген дәлелдеме сертификатының g(n) битін ғана тексеруге болады (негізінен кездейсоқ кіруді пайдаланады). PCP кластарының әртүрлі түрлері туралы дәлелдеу оңай нәтижелер бар. 1 = PCP(0, poly), кездейсоқтық жоқ, бірақ сертификатқа қол жеткізімі бар полиномиалдық уақыт машиналарының класы, NP-ға тең. 1 = PCP(poly, 0), полиномиалдық уақыт машиналарының класы полиномиалдық көлемдегі кездейсоқ биттерге қол жеткізімі бар RP-ға тең. Арора мен Сафраның алғашқы маңызды нәтижесі мынадай болды; яғни, егер NP протоколындағы тексеруші дәлелдеме сертификатынан қарау үшін тек O(log n) бит таңдауға шектелген болса, бұл ешқандай айырмашылық жасамайды, егер ол O(log n) кездейсоқ битті пайдалануға мүмкіндігі болса. Сонымен қатар, PCP теоремасы дәлелдемеге қол жеткізу санын тұрақтыға дейін төмендетуге болады деп мәлімдейді. Яғни, 1 = NP = PCP(log, O(1)). Олар NP-нің осы құнды сипаттамасын P = NP болмаса, белгілі бір NP-толық проблемалардың оптимизациялық нұсқалары үшін жуықтау алгоритмдерінің жоқ екенін дәлелдеу үшін қолданды. Мұндай проблемалар қазір жуықтаудың қиындығы деп аталатын салада зерттеледі.
Оқулық
Арора, Санжиев; Барак, Боаз, "Көңілдік теориясы: заманауи тәсіл", Кембридж университетінің баспасы, 2009 жылдың наурызы. 10.4 бөлім: Интерактивті дәлелдеу жүйелері, 354–366 бб. 19.2 бөлім: Табиғатқа қарсы ойындар және интерактивті протоколдар, 469–480 бб.