Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 15.3 Интерактивные системы доказательства с нулевым разглашением Вверх: 15. Основные понятия теории доказательств с нулевым разглашением Назад: 15.1 Введение   Содержание   Предметный указатель


15.2 Интерактивные системы доказательства

Теория доказательств с нулевым разглашением базируется на понятии интерактивной системы доказательства (interactive proof system), которое было введено в 1985 году независимо в работах Бабаи [Bab] (окончательный вариант [BMo]) и Гольдвассер, Микали и Ракоффа [GMR1] (окончательный вариант [GMR2]). К настоящему времени это понятие стало предметом изучения довольно представительной ветви теории сложности вычислений, имеющей глубокие связи с другими разделами теории.

Мы предполагаем известными понятия детерминированной и недетерминированной машины Тьюринга (см. [ГДж], [АХУ]) и языка, распознаваемого детерминированной или недетерминированной машиной. Для единообразия обозначений везде в этом подразделе мы будем обозначать через $ L$ язык в двоичном алфавите, т. е. произвольное множество, состоящее из конечных строк из нулей и единиц. Через $ x$ или $ w$ мы будем обозначать слово в том же алфавите, которое подается на вход машины Тьюринга, а через $ n$ -- его длину. Время работы детерминированной (недетерминированной) машины Тьюринга на входе $ w$ -- это (максимально возможное) количество тактов ее работы на этом входе. Если существует некоторый полином, который ограничивает сверху время работы машины Тьюринга на входах длины $ n$ для всех достаточно больших $ n$, то машину будем называть полиномиальной. Языки, которые распознаются полиномиальными детерминированными (недетерминированными) машинами Тьюринга, образуют класс P (NP).

Память, которая расходуется детерминированной машиной Тьюринга на входе $ w$ -- это количество ячеек рабочей ленты, используемых в ходе работы машины на этом входном слове. Если она (память) ограничена полиномом от $ n$, то язык, распознаваемый этой машиной, по определению, принадлежит классу PSPACE.

Эквивалентное определение класса NP следующее. Язык $ L$ принадлежит классу NP тогда и только тогда, когда существует двуместный предикат $ Q(w,u)$, определенный на таких парах слов $ w$ и $ u$, что длина $ u$ ограничена некоторым полиномом от длины $ w$, и вычислимый полиномиальной детерминированной машиной Тьюринга, такой что

$\displaystyle w\in L\iff\exists u\ Q(w,u)=1. $

Класс coNP состоит в точности из языков, дополнения к которым лежат в классе NP, и также может быть определен вышеизложенным способом с помощью соотношения

$\displaystyle w\in L\iff\forall u\ Q(w,u)=0. $

В нашем дальнейшем изложении встречаются понятия NP-полного и PSPACE-полного языка. Язык $ L$ называется полным в классе $ K$, если он принадлежит этому классу и для любого языка $ L'$ из класса $ K$ существует функция $ f$, вычислимая детерминированной полиномиальной машиной Тьюринга и такая, что для произвольного $ w$

$\displaystyle w\in L'\iff f(w)\in L. $

Таким образом, вопрос о существовании какой-либо эффективной процедуры для всех языков из класса $ K$ сводится к вопросу о существовании этой процедуры для $ K$-полного языка.

Вероятностная машина Тьюринга -- это обычная (детерминированная) машина Тьюринга, снабженная дополнительной лентой, на которой записывается случайное слово. Говоря неформально, машина имеет возможность подбрасывать монету и совершать то или иное действие в зависимости от результата. Вероятностная машина Тьюринга распознает язык $ L$, если на входе $ w\in L$ она выдает положительный ответ с вероятностью не менее $ 2/3$, а на входе $ w\notin L$ с вероятностью не более $ 1/3$, где вероятность берется по равномерному распределению случайных слов (одинаковой длины). Таким образом, вероятность ошибочного ответа машины на любом входе не превосходит $ 1/3$.

Класс BPP содержит языки, распознаваемые вероятностными машинами Тьюринга с полиномиальным ограничением на время работы. Важно отметить, что по всякой полиномиальной вероятностной машине Тьюринга $ M$ можно построить полиномиальную вероятностную машину $ M'$, распознающую тот же язык, но с вероятностью ошибки менее чем $ 1/2^{p(n)}$ для заданного полинома $ p(n)$. Программа работы машины $ M'$ следующая. На входе $ w$ $ 24p(n)$ раз моделируется работа машины $ M$ на этом же входе, каждый раз с независимым выбором случайного слова. Ответ машины $ M'$ совпадает с наиболее часто встречающимся ответом в моделированиях работы машины $ M$.

Интерактивная система доказательства -- это игра двух участников, которых мы будем называть игроками $ P$ (Prover), или доказывающим, и $ V$ (Verifier), или проверяющим. Перед игрой формулируется некоторое утверждение $ S$ (например, что некоторый объект $ w$ обладает свойством $ L$). В ходе игры $ P$ и $ V$ обмениваются сообщениями. В конце игры игрок $ V$ выносит окончательное решение, является ли $ S$ истинным или же ложным. Цель игрока $ P$ -- убедить игрока $ V$ в том, что $ S$ истинно. При этом игрок $ P$ может мошенничать и целью игрока $ V$ является проверка аргументов игрока $ P$. Игрок $ V$ имеет ограниченные вычислительные возможности, а именно -- время его работы ограничено некоторым полиномом от длины $ w$, и самостоятельно, без помощи игрока $ P$, он не способен распознать истинность утверждения $ S$. Вычислительные возможности игрока $ P$ никак не ограничиваются, что в действительности может соответствовать ситуации, когда $ P$ владеет какой-то трудно получаемой информацией (хотя, напомним, он может и блефовать, утверждая, что такая информация у него имеется). Таким образом, программа действий игрока $ V$ должна быть устроена так, что во-первых, в случае $ S$ -- истинно, игрок $ P$ может убедить игрока $ V$ признать это;

во-вторых, в случае $ S$ -- ложно, игрок $ P$ не сможет убедить $ V$ в противном, какие бы аргументы он не выдвигал (т. е., вне зависимости от получаемых от $ P$ сообщений, $ V$ в этом случае делает вывод, что $ S$ ложно).

Добавим, что игроки $ V$ и $ P$ в ходе игры могут подбрасывать монету (каждый свою и втайне друг от друга), и использовать результаты этих подбрасываний при выполнении своих действий. Мы допускаем, что игрок $ V$ может иногда ошибаться, но требуем, чтобы вероятность принятия им неправильного решения была пренебрежимо малой.

Формализацию описанной модели мы приводим ниже, после неформального обсуждения и примеров.

Пусть $ S$ -- это утверждение вида $ w\in L$, где $ w$ -- слово, а $ L$ -- язык в двоичном алфавите. Если существует интерактивная система для доказательства утверждений такого сорта, то мы говорим, что язык $ L$ обладает интерактивной системой доказательства (или протоколом интерактивного доказательства, или просто интерактивным доказательством). Из пока неформального определения интерактивного доказательства вытекает, что языки из классов NP и BPP обладают довольно простыми интерактивными доказательствами. В случае языка из NP игрок $ V$ моделирует детерминированным образом работу полиномиальной недетерминированной машины Тьюринга, запросив подсказку у игрока $ P$. Такой подсказкой может служить так называемая догадка (witness) для входного слова. Например, если входным словом является формула пропозиционального исчисления, выполнимость которой требуется распознать, то догадкой является набор значений аргументов, на котором эта формула истинна. Подчеркнем, что игрок $ P$ имеет неограниченные вычислительные возможности и поэтому он всегда может найти требуемый набор значений аргументов, если только такой существует. В случае языка из BPP игрок $ V$ непосредственно моделирует работу соответствующей полиномиальной вероятностной машины Тьюринга и не нуждается в подсказках игрока $ P$.

Первый нетривиальный пример интерактивного доказательства был предложен в [GMR1] для языка КВАДРАТИЧНЫЕ НЕВЫЧЕТЫ (QUADRATIC NONRESIDUE, сокращенно QNR), состоящего из таких пар $ (y,x)$ взаимно простых натуральных чисел, что $ y<x$ и $ y$ не является квадратичным вычетом по модулю $ x$, т. е. не существует $ z$ такого, что $ z^{2}\equiv y\mkern5mu({\rm mod}\,\,x)$. Положим $ n=[\log x+\log y]$. Ниже мы считаем, что умножение происходит в группе $ \mathbb{Z}^{*}_{x}$ натуральных чисел, меньших чем $ x$ и взаимно простых с ним. Пересылку сообщения $ v$ от игрока $ V$ игроку $ P$ мы будем записывать $ V\longrightarrow P:v$, а сообщения $ u$ от игрока $ P$ игроку $ V$ -- как $ P\longrightarrow V:u$. На входе $ (y,x)$ (т. е., $ S$ -- это утверждение $ (y,x)\in{}$QNR), игра происходит следующим образом:

    $ V$: для $ i=1,\ldots,n$ выбирает случайные биты $ \alpha_i$ и случайные натуральные числа $ z_i<x$, взаимно простые с $ x$;

    $ V\longrightarrow P$: $ v_{i}=\begin{cases} z^{2}_{i},&\text{если }\alpha _{i}=0,\\ yz^2_i,&\text{если }\alpha_{i}=1 \end{cases}$ для $ i=1,\ldots,n$;

    $ P\longrightarrow V$: $ \beta_{i}$, $ i=1,\ldots,n$;

    $ V$: если $ \alpha _{i}=\beta _{i}$ для всех $ i$, то дает положительный ответ, иначе -- отрицательный.

Таким образом, игрок $ V$ втайне от $ P$ подбросил монету $ n$ раз, получив последовательность $ \alpha_{1},\ldots,\alpha_{n}$. Далее, по каждому биту $ \alpha_{i}$ он вычисляет, опять используя случайность, число $ v_{i}$ и посылает эти числа игроку $ P$, требуя, чтобы тот восстановил исходную последовательность $ \alpha_{1},\ldots,\alpha_{n}$. Заметим теперь, что в случае $ (y,x)\in{}$QNR значения $ \alpha_{i}$ определяются однозначно по значениям $ v_{i}$, а именно $ \alpha _{i}=0$ тогда и только тогда, когда $ v_{i}$ -- квадратичный вычет по модулю $ x$. Следовательно, в этом случае игрок $ P$ может вычислить $ \alpha_{i}$ и тем самым убедить игрока $ V$ дать положительный ответ (с вероятностью $ 1$). Если же $ (y,x)\notin{}$QNR, то $ v_{i}$, которые получает $ P$, -- это просто случайные квадратичные вычеты по модулю $ x$, и понятно, что какую бы последовательность $ \beta_{i}$ не послал игрок $ P$, для каждого конкретного $ i$ $ \alpha _{i}=\beta _{i}$ с вероятностью $ 1/2$, а значит для всех $ i$ равенство $ \alpha _{i}=\beta _{i}$ будет выполнено с вероятностью $ 1/2^{n}$. Таким образом, если $ (y,x)\notin $QNR, то игрок $ V$ выдаст положительный ответ лишь с этой экспоненциально малой вероятностью.

Следующий пример эксплуатирует по существу ту же идею и появился в работе Гольдрайха, Микали и Вигдерсона [GMW1] (окончательный вариант [GMW2]). Теперь мы опишем интерактивную систему доказательства для языка НЕИЗОМОРФИЗМ ГРАФОВ (GRAPH NONISOMORPHISM, сокращенно GNI), состоящего из всех пар $ G_{0}$ и $ G_{1}$ неизоморфных между собой графов. Графы называются изоморфными, если существует взаимно однозначное соответствие между их вершинами, при котором соединенным ребром вершинам в одном графе соответствуют соединенные вершины в другом графе. Очевидно, не упрощая задачи, мы можем предполагать, что $ G_{0}$ и $ G_{1}$ -- это графы на одном и том же множестве вершин $ N$ мощности $ m$.

    $ V$: для $ i=1,\ldots,m$ выбирает случайный бит $ \alpha_i\in\{0,1\}$ и, случайным образом перенумеровав вершины графа $ G_{\alpha_{i}}$, получает граф $ G^{i}$;

    $ V\longrightarrow P$: $ G^{i}$, $ i=1,\ldots,m$;

    $ P\longrightarrow V$: $ \beta_{i}$, $ i=1,\ldots,m$;

    $ V$: если $ \alpha _{i}=\beta _{i}$ для всех $ i$, то дает положительный ответ, иначе -- отрицательный.

Как легко видеть, все рассуждения, которые мы провели для интерактивной системы для языка QNR, с очевидными изменениями остаются в силе и для описанной системы для GNI.

Ниже мы даем определение интерактивной системы доказательства $ \langle V,P\rangle $ для языка $ L$, введенное Гольдвассер, Микали и Ракоффом [GMR1].

Пусть $ V$ -- полиномиальная вероятностная машина Тьюринга; $ P$ -- вероятностная машина Тьюринга без ограничений на сложность. Машины $ V$ и $ P$ имеют общую входную ленту, на которой записывается входное слово $ w$, и с которой они могут только считывать информацию. Кроме того, они имеют общую ленту для обмена сообщениями. Каждая из машин $ V$ и $ P$ считывает предыдущую запись, сделанную другой из них, и делает собственную очередную запись (т. е., машины $ V$ и $ P$ работают в режиме диалога -- после отправки сообщения каждая из них переходит в состояние ожидания до получения ответа). Под очередным раундом мы понимаем очередную передачу сообщения машиной $ V$ машине $ P$, а затем и сообщения машины $ P$ машине $ V$ (или наоборот, в зависимости от того, кто согласно протоколу инициирует диалог). Если в результате описанных обменов сообщениями машина $ V$ останавливается в принимающем состоянии (выдает положительный ответ), то мы говорим, что $ P$ убеждает $ V$.

Система $ \langle V,P\rangle $ является интерактивной системой доказательства для языка $ L$ (представляет интерактивный протокол для $ L$, распознает язык $ L$), если выполнены следующие условия:     1) если $ w\in L$, то $ P$ убеждает $ V$ с вероятностью не менее $ 2/3$,

    2) если $ w\notin L$, то какова бы ни была машина $ P'$, она убеждает $ V$ с вероятностью не более чем $ 1/3$. В литературе по интерактивным протоколам условие 1 называется полнотой (completeness), а условие 2 -- корректностью (soundness) протокола.

На языке приведенного выше неформального описания машины $ V$ и $ P$ -- это игроки $ V$ и $ P$. Если для некоторого языка задана интерактивная система $ \langle V,P\rangle $, то игрок $ P$ в отличие от $ P'$ будет называться честным. Класс языков, обладающих интерактивными системами доказательства, обозначается IP. Класс языков, для которых существуют интерактивные системы с ограничением $ k$ на количество раундов, обозначается IP$ (k)$. Здесь $ k=k(n)$ -- некоторая функция от длины входа, которая, очевидно, не может превышать время работы машины $ V$ и, следовательно, ограничена некоторым полиномом от $ n$.


Замечания

1. Как вытекает из определения, очередное сообщение $ u_{i}$ игрока $ V$ игроку $ P$ зависит от входного слова $ w$, сообщений $ v_{1},\ldots,v_{i-1}$, полученных в предыдущих раундах от игрока $ P$, и от результатов $ r$ подбрасывания монеты игроком $ V$. Отметим, что $ u_{i}(w,v_{1},\ldots,v_{i-1},r)$ -- полиномиально вычислимая функция. Очередное сообщение $ v_{i}$ игрока $ P$ является функцией произвольной сложности от входного слова $ w$, уже полученных им от игрока $ V$ сообщений $ u_{1},\ldots,u_{i}$, и результатов подбрасывания собственной монеты. Окончательный ответ игрока $ V$ является значением полиномиально вычислимого предиката $ Q(w,r,u_{1},v_{1},\ldots ,u_{k},v_{k})$.

2. Интерактивная система $ \langle V,P\rangle $ может быть задана только программой игрока $ V$. Честного игрока $ P$ можно определить требованием следовать оптимальной стратегии, чтобы убедить $ V$. Таким образом, можно в частности считать, что $ P$ -- детерминированная машина Тьюринга. Однако возможность делать случайный выбор будет существенна в определении систем доказательства с нулевым разглашением.

3. Из определения вытекает, что если $ \langle V,P\rangle $ -- интерактивная система доказательства для некоторого языка, то как количество раундов, так и длины сообщений, которыми обмениваются $ V$ и $ P$ заведомо не превосходят времени работы машины $ V$ и, следовательно, ограничены некоторым полиномом от $ n$.

4. Как вытекает из пунктов 1 и 2 определения, мы допускаем вероятность ошибки не более чем $ 1/3$. Определение останется эквивалентным исходному, даже если мы потребуем ограничить вероятность ошибки экспоненциально малой величиной, скажем $ 1/2^{n^{c}}$ для некоторой константы $ c$. Это следует из возможности применения стандартного преобразования вероятностного алгоритма, описанного в разделе 15.2, и легко усматривается из приведенных выше примеров. При этом не обязательно увеличивать количество раундов протокола. Независимые выполнения протокола можно организовать параллельно, т. е. в очередной раунд передавать несколько экземпляров независимых сообщений (как в описанных выше протоколах для языков КВАДРАТИЧНЫЕ НЕВЫЧЕТЫ и НЕИЗОМОРФИЗМ ГРАФОВ). В этом случае увеличивается в полиномиальное число раз только длина передаваемых сообщений.


Выше были отмечены включения сложностных классов NP и BPP в класс IP$ (1)$ и доказано, что языки QNR и GNI тоже лежат в IP$ (1)$. Для языка QNR известно его включение в класс NP$ {}\cap{}$coNP, вопрос о принадлежности языка GNI классам NP или BPP открыт.

Естественным образом возникает вопрос: какие языки обладают интерактивными системами доказательства, т. е. каков объем класса IP. Долгое время об этом ничего не было известно, кроме несложно устанавливаемых соотношений

   NP$\displaystyle {}\cup{}$BPP$\displaystyle {}\subseteq{}$IP$\displaystyle {}\subseteq{}$PSPACE$\displaystyle .$

Полностью вопрос был решен в 1989 году в работах Фортноу, Карлоффа, Лунда и Нисана [FKLN] и Шамира [Sha], где была предложена интерактивная система доказательства для PSPACE-полного множества. Отсюда следует, что интерактивными доказательствами обладают в точности языки, распознаваемые с полиномиально ограниченной памятью.

Теорема 1.  IP$ {}={}$PSPACE.

Упрощенное доказательство этого факта предложено в [She].

Таким образом, оказалось, что интерактивные системы доказательства имеют довольно большие возможности. Можно даже сказать, что этот результат был в достаточной степени неожиданным: до его появления многие исследователи считали, что класс IP не может быть значительно шире класса NP (хотя соотношение между классами NP и PSPACE до сих пор не выяснено, представляется правдоподобным, что класс PSPACE существенно шире).

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 15.3 Интерактивные системы доказательства с нулевым разглашением Вверх: 15. Основные понятия теории доказательств с нулевым разглашением Назад: 15.1 Введение   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100