Мультиинтерактивные системы доказательств с постоянным количеством раундов и их применения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГБ р Г Б ' Ой'

¿¿и I -

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ р Г Ь « Н имени М.В. ЛОМОНОСОВА

Механпко-математический факультет

На правах рукописи УДК 510.52

ВЕРБИЦКИЙ Олег Васильевич

МУЛЬТИИНТЕРАКТИВНЫЕ СИСТЕМЫ ДОКАЗАТЕЛЬСТВ С ПОСТОЯННЫМ КОЛИЧЕСТВОМ РАУНДОВ И ИХ ПРИМЕНЕНИЯ

01.01.06—математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва—1994

Работа выполнена, ва кафедре математической логики механико-математического факультета Московского государственного университета. им. М.В. Ломоносова

Научные руководители:

Официальные оппоненты:

член-корресдодент РАН, профессор СЛ. Адяе; доктор физкко-математических наук, в.н.с. A.A. Разборов.

доктор физико-математических наук, с.н.с. В.М. Садельников; кандидат физико-математических наук, Н.К. Верешагнп.

Ведущее учреждение:

Вычислительный центр РАН.

■/ff- llwuf

1 Зашита диссертации состоится " / " 1994 г. в

16 час. 05 мин. на заседании специализированного Совета Л 053.05.05 дра Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, гуд. 14-08." "" ■

ГУ - 1

О диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (14 этаж).

Автореферат разослан

/У" ¿¿¿<2jJ

. 1S94 г.

Ученый секретарь специализированного Совета д.053.05.05 при МГУ, док-тор физико-математических наук, профессор

В.Н.Чубарихов

1 Общая характеристика

Мультиинтсрактивнал система, доказательств является Егроятностной недетерминированной вычислительной моделью для распознавания языка L, в которой полиномиально ограниченный игрок V, обмениваясь сообщениями с изолированными друг от друга игроками Pi, '..., Pf, должен принять решение, принадлежит ли языку L входное слово ш. При этом вероятность принято« ошибочного решения должна быть небольшой.

В настоящее врем* исследования по интерактивным доказательствам оформились в довольно представительный раздел теории сложности вычислений. Обнаружены многочисленные применения результатов из этой области к задачам криптографии, слоясносткой классификации оптимизационных задач, к структурным вопросам теории сложности.

В [1] было показано, что ограничение количества игроков Pj,..., Pi до двух не сужает класса языков, распознаваемых мультиинтерактивньши системами. При этом важной характеристикой сложности мультиинтер-ахтивной системы становится количество обменов сообщениями игрока V с игроками Pi и Pi (количество раупдов).

Предметом изучения настоящей диссертации являются мультяинтер-активные системы доказательств с ограниченным количеством раундов. Основная цель диссертации — рассмотрение некоторых естественных процедур преобразования заданной мультиинтерактивной системы (V, Рг, Р2) в систему (V,Pi,P-2) с постоянным числом раундов и исследование вопроса о корректности последней (т.е..вопроса,.расцознает ли. система {V, Ри Р?) язык, распознаваемый системой (V,Pi,Pi)).

В диссертации получены следующие новые результаты. Обоснована корректность естественного способа сокращения числа раундов, который позволяет провести любое мультиинтерактивное доказательство при количестве раундов, ограниченном константой . Решена открытая проблема о параллельном выполнении мультиинтерактивного доказательства. С использованием мультиинтерактпвных систем с ограниченным числом раундов установлена вычислительная трудность некоторых оптимизационных задач.

'М. Ben-Or, S. Goldwasser, J. Kilian, and A.. Wigderson. Multi-prover interactive proofs: how to remove intractability assumption. In Proc. of the 20iA ACM Ann. Symp. on lie Theory of Corr.pviwj (STOC), pages 113-131, 1988.

Апробация работы. Результаты диссертации докладывались на 1оой Конференции молодых ученых МГУ, посвященной 90-летию со дня рождения А.Н.Колмогорова (1993 г.), международной конференции "Вероятностные доказательства и их применения к проверке программ, криптографии и трудности аппроксимации" (Институт Вайпмана. Реховот, Израиль, 1994 г.). семинарах кафедры математической логики МГУ. совместном семинаре МИ РАН и ВЦ РАН по теории сложности вычислений.

Публикации. Результаты диссертации опубликованы в работах, список которых приведен в конце автореферата.

Структура диссертации. Диссертация состоит из введения и трех глав, разбитых на десять параграфов. Общий объем диссертации—73 страницы. Нумерация утверждений, определений и замечаний отдельная для каждой глазы и отражает их расположение относительно параграфов. Исключение составляют теоремы, являющиеся основными результатами диссертации, для которых принята однозначная нумерация. Леммы, служащие основным техническим средством при доказательстве этих теорем, имеют такую же нумерацию.

2 Содержание работы

Формальное определение мультшштерактивной системы доказательств (V, Р\,..., Р|) для языка Ь ([1]) приведено в пункте "Основные определения" во введении. Пусть V—вероятностная мамина Тьюринга, время работы которой на входе ги ограничено некоторым полиномом от его ллнны п; Р],..., Р( — детерминированные машины Тьюринга (никакие ограничения на их вычислительные возможности не накладываются). Машины V, Р\,..., Р/ имеют общую входную ленту, на которой записывается вход ш, и с которой они могут только считывать информацию. Кроме того, машина V имеет общую ленту с каждой из Р-,,..., Р1 для обмена сообщениями. Каждая из двух машин V и Ри. для всех V < I, считывает предыдущую запись, сделанную другой из них, и делает собственную очередную запись. Машины Рг,...,Р1 не имеют средств для обмена информацией между собой. Под очередным раундом мы понимаем очередную передачу сообщений игроком V игрокам Рх,..., Р( и сообщений этих

игроков игроку V. Если в результате описанных обменов сообщениями машина V остановлигается на входе ш в принимающем состоянии, то мы говорим, что Pi,...,Pi убеждают V.

Система (V,Pt,..., Р/) является мулътииитерактивной системой доказательств для языки L (представляет мультиинтперактпивны-й протокол д.ч L), если выполнены следующие условия.

1. Если w G L, то Я,,..., Pt убеждают V с вероятностью не менее 2/3.

2. Если w fc L, то каковы бы ни были Р[,..., Р{, они убеждают V с вероятностью, не превышающей 1/3.

Машины V, Рь ..., Л мы называем игроками V, Pi,..., Р/.

Класс языков, обладающих мультиинтерактивными системами доказательств, обозначается Ml Р. Класс языков, для которых существуют мультиинтерактивные системы {V, Р\,..., Pi) с ограничением 1с на количество раундой. обозначается 1Р(1, к).

Глава 1 организована следующим обазом. В §1 приведены результаты из [2], которые используются при доказательстве основного результата этой главы — теоремы 1. В §2 формулируется лемма 1, являющаяся основным техническим средством в главе 1, и на ее основании доказывается теорема 1. В §3 доказываются некоторые вспомогательные утверждения, нужные для доказательства леммы 1, которой занимает §4.

-Теорема 1 Jf.is некоторой константы с гыассы М1Р -и IР('2. с) совпадают.

Отметим, что мы придерживаемся данного в [1] определения муль-тиинтерактивпой системы доказательств, где вероятность ошибки ограничена постоянной 1/3. Из доказательства теоремы 1 вытекает оценка с < 324.

JL. Babai, L. Fortnow, and С. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, l(l):3-40, 1991.

Теорема 1 получека независимо от работ других авторов ¡3. 4. 5], о которых автор диссертации узнал в процессе подготовки своей статьи [6] осенью 19У1 года. После того как эта статья была сдана в печать, появилась работа [7], в которой получен окончательный результат в этом направлении, а цуеано, доказано, что MIP — IP(2,1) с экспоненциально низкой вероятностью ошибки. Метод, который предложен в [6] и излагается в настоящей диссертации, принципиально отличается от методов работ [4,5,7].

Все перечисленные работы исходят из наличия длг любого языка L из класса MIP системы доказательств {V, Рх, Р2). ограничивающейся одним раундом, но имеющей вероятность ошибии 1 — 1 /пс ([2]). Далее эта система будет упоминаться как протокол П. Повторение протокола П последовательно nc+I раз позволяет уменьшить эту ошибку до экспоненциально малой величины (1 — l/nc)n'*' ~ е~п, однако требует возрастающего числа раундов. В перечисленных ьыше работах предложены различные способы преобразования исходного протокола П, уменьшающие вероятность ошибки без увеличения числа раундов.

По сравнению с [4,5,7] используемый в настоящей диссертации метод является наиболее непосредственным способом псрсиыелъного повторения протокола П и приводит к протоколу, вопрос о корректности которого в силу его естественности представляет и самостоятельный интерес. Суть этого метода сводится к следующему.

Протокол П включает в себя проверку того, действительно ли игрок Р|, получив сообщение (хь... ,ifc) от игрока V, выдает в ка-

3J. Kilian. Strong separation models of multi-provcr interactive proofs. DIMAGS Workshop on Cryptography, 1990.

4U. Feige. On the success probability of the two prover ir. one round proof systems. In Я roc. of the 6 th Am. Conftrtnct on Structure i» Complexity Theory, pages 116-123, 1991.

SD. Lapidot and A. Shamir. Fully parallelized multi-prover protocol for NEXP-time. In Proc. of ike 32лi IEEE Ann. Symp. on Foundations of Computer Science (FOCS), pages 13-18, 1991.

eO.B. Вербицкий. О возможности проведения любого мультиннтерактивного доказательства за ограниченное число раундов. Изьестия РАН. Сер■ мат., 57(3):152-178, 1893.

'U. Feige and L. Lovasz. Two-prover one-round proof systems: their power and their problems. In Proc. of the 24<4 ACM Ann. Symp. on the Theory of Computing (STOC'), pages 733-744, 1992.

честве своего сообщения (уь..., у к) вектор (/1(11),.. .,Л(ц)), где Л — некоторая функция, или же он "хитрит", посылая игроку V вектор (Л1 (х\,...,Хк),...,Ьь{х\,...,2к)). Для осуществления этой проверки пгрок V случайным образом выбирает к из множества {1 и посылает другому игроку Рг сообщение х«. Получив от Рг ответ у, игрок V сравнивает ук с у, и если они не совпадают, то прекращает игру и выдает отрицательный ответ. Как легко видеть, "хитрость" игрока Рх будет распознана с вероятностью по крайней мере ^т1ПАР[Р|(г1,... ,Хк) ф (Л(х1),..., Л(х*))], где вероятность берется по распределению вектора (хь... , хь). Чтобы увеличить эту вероятность и таким образом уменьшить вероятность ошибки, в [2], как и во всех предшествующих работах по мультиинтерактивным доказательствам, использовалось последовательное и независимое повторение этого процесса I раз, где / = 1{к)—некоторый полипом, что требовало возрастачэ-щего количества раундов.

В диссертации обосновывается корректность параллельной версии описанной выше процедуры, в которой игрок V посылает игроку Р\ сразу все I выбранных случайно и независимо экземпляров вектора (х[,... ,а т.е. вектор (х[,..., х\,... ,х[,... а игроку Р2—вектор (г^,... ,£),,), поменяв а нем предварительно порядок компонент в соответствии со случайной перестановкой тг (см. лемму 1 диссертации).

Глава 2 диссертации посвящена вопросу об эффективности процедуры уменьшения вероятности ошибки мультипцтерактивного .протокола, (например, упомянутого выше протокола П), которая заключается з его непосредственном параллельном повторении. Вопрос этот в настоящее время является открытым. Полученные в главе 2 результаты дают положительный ответ на ослабленную форму этого вопроса.

Изучаемая проблема имеет следующую теоретико-игровую постановку, которая пригодится в §1. Рассматривается игра (? двух участников. Пусть X, У, 5, Т—конечные множества, ф—1предикат на X х У х 5 х Т. Пара (х,у) выбирается случайным образом из множества С X х У. х посылается игроку. 1, а у—пгрску 2. Игроки 1 п 2 выдают ответы /(х) € 5 и Н(у) 6 Т в соответствии со своими стратегиями / : X —► 5 и А : У —> Т. Если Ф(х,у, /(г), А(у)) = 1, то оба игрока выигрывают; в противном случае они проигрывают. Цель игроков i и 2—сообща максимизировать вероятность выигрыша. Вероятность выигрыша для

оптимальных стратегий игроков обозначается u;(G). Таким образом.

-»(G) = iraxP[0(rii,,/(x),%})= 1]. jji

Игра G называется нг.триьпалъной, если ui(G) ф 1.

Игра G" определяется как выполнение игры G параллельно п раз.

Белее формально, набор ((xi,yi)____,{хп,уп)) выбирается случайным

образом из Q". Игрокам 1 и 3 открываются векторы х — и У — (ïii•■■■,Уп), соответственно. Они выдают ответы F(x) =

(/i(ï),. ■ ■, /„(i )) и fi (у) — (hi(y),____Л„(з)). Теперь игроки выигрывают

в случае Д,"=1 = 1, и

w(Gn) = maxP [Я о(Х;,у;,!{{£),Ш) = ij •

Единственные известные сейчас сотношения между ui{(?) и сле-

дующие:

(w(G)Y <*(G")<u{G).

Корректность параллельного выполнения протокола П вытекала бы из факта быстрого стремления u(G") к 0 при п —» ос. Однако, в [4] построен пример нетривиальной игры G. для которой и>(G2) — u(G). Вопрос о поведении величины ùj(G") при п. стремящемся к бесконечности, исследовался в работах [4,7]. Тем ке менее, не было даже известно, существует ли для любой- игры G такое п, Что wfG") < u.'(G)" (см.'обсуждение 'а [7])".

Основным результатом главы 2 является следующее утверждение, доказанное в §2, которое дает положительный ответ на ьопрос, поставленный в [4].

Теорема 2 Если G—нетривиальна! игра, moui(Gn) —* 0 при п —» оо.

Доказательство теоремы 2 основано на лемме 2, которая устанавливает связь рассматриваемой проблематики с плотносткым аналогом классической теоремы Халеса-Джеветта в теории Рамсея ([8]). Пусть А = {в},... ,at} — ¿-элементное множество, ш(г) — элемент множества (A U {г})п, где z — переменная для элементов множества А, которая

гН. Fursleaberg and Y. Katznelson. A density version of the Hales-Jewett theorem. Journal d'Analyse Mathématique, 57, 1991.

обязательно присутствует в и>(г). Множество {ti'(ai),____называется комбинаторной прямой в Лп. Лемма 2 диссертации утверждает, что ^.•(С1) не превышает .максимальной плотности подинсжества множества Qn, ке содержащего комбинаторных прямых, которая, как доказано в [8]. ярляется бесконечно малой величиной при возрастающем параметре гг.

Главг: 3 диссертации посвяшепа применениям результатов о мульти-интерактивных доказательствах с ограниченным числом раундов к классификации сложности некоторых оптимизационных задач. Исследуются следующие задачи.

1. Максимальное ■чиело -независимых к-уголъникоз (fc-GON), к > 2. Задан: граф G. Найт^: максимальное число попарно независимых к-угольников, ¿-угольником в графе называйте» цикл размера к. Два /¿-угольника называются независимыми, если всякое ребро графа G, одна вершина которого принадлежит одному t-угольнпку. а etc рая—другому, принадлежит по крайней мере одному из этих ¿-угольников.

2. Максимальное число согласованных кхък размера к (к-CON), к > 2. Задан: граф G на множестве вершин И = Uf=1Ari, где для каждого г множество JVj независимо d G (т.е. никакие две вершины из Ni не соединены ребром); JV, = UjNij и все множества Ni:] попарно различны. Найти: максимальное число клик размера к в G .таких, что для произвольных i,j не более чем одна вершина из Nij принадлежит какой-либо из этих клик. (Такпе клики названы согласованными.)

3. MAX|0gn,n- Задгно: т конъюнкций, каждая из которых состоит из не более, чем log т пропозициональных переменных или их отрицаний. Найти: максимальное число кочыояхпий, которые могут быть выполнены одним и тем же набором значений истинности для переменных.

Подробное обсуждение этих задач содержится в §2 главы 3. Формулировки 1 и 2 задают семейства задач к-GON и /fc-CON. где к — натуральный параметр. Задача 3 рассматривалась в [9].

9Р. Berm&u Mid G. ScHnitger.-Oa the complexity of approximating the Independent

Решить оптимизационную задачу на входе I означает вычислить ее эптимальпое зяатеиие opt(I) € N (формальные определения оптимизационной NP-задачн в связанных с оптимизационными NP-задачами понятий приведены в §1). Функция opt(l) часто оказывается NP-трудной, что имеет место, в частности, для определенных выше задач. Оптимизационная задача называется аппроксимируемой с точностью до множителя с, если существует вычислимая за полиномиальное время функция g(I) такая, что opt(l) < g(í) < с- opt(I) для всех I. Для каждой конкретсой NP-трудной оптимизационной задачи важно установить, является ли она аппроксимируемой (с точностью до некоторого постоянного множителя), или же ее аппроксимация все еще NP-трудна.

Основным результатом главы 3 является следующее утверждение, которое устанавливается в §3.

Теорема 3 i) Eaat хотя бы одна из задач k-GON для к > 3 или к-CON для к > 2 аппроксимируема с точностью до множителя с £ (1,4/3), то tiP = Р.

ii) Если хотя бы одна из задач k-GON для к > 3 или k-CON для к >'.2

аппроксимируема с точностью до множителя с > 1, то NP Ç £>Г/ЛГ£(п0(Ьв*))-

iii) Если задача. k-CON для к > 4 аппроксимируема с точностью до " мчожит'ёля с >"1, то NP = Р...........•

iiii) Если задача MAXiogn,n аппроксимируема с точностью до миожи-теля с > 1, зал NP = Р.

Для доказательства теоремы 3 используется мультиинтерахтивный протокол с огрангченпым числом раундов в контексте основной идеи работы [10], где била обнаружена применимость понятия общей муль-тиинтерактивной системы для обоснования трудности аппроксимации задачи MAX CLIQUE вычисления размера наибольшей клики в графе.

Set problem. In Proca&ngs of the STACS'89, Lecture Notes in Computer Science, 349, pages 256-268, Springer-Verfcig, New York/Berlin, 1989.

I0U. Feige, S. Goldmsser. !.. Lorász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In Aoc. oftke32nd IEEE Ann. Spnp. oa Foundations of Computer Science (FOCS), pages 2-12, 1991.

Каждая из имеющихся процедур сокращения количества раундов, в том числе и процедура, описанная в главе 1 диссертации, позволяет доказывать утверждения теоремы 3 для некоторых значений с н условий вида NP С DT¡ME ( п 8 "J. Наиболее эффективные результаты, которые и сформулированы выше, получаются с использованием процедуры из [7]. примененной не к базисному протоколу П, а к протоколу, разработанному

Утверждения теоремы 3 представляют интерес с точки зрения логической классификации оптимизационных NP-задач, предложенной в [12, 13]. Рассмотренные задачи MAXiogn,„, к-GON, к-CON попадают в класс RMAX(2) этой классификации (определения см. в §1). Класс RJVIAX(2) занимает в логической классификации особое место, Tas как классы, имеющие более простое логическое задание, состоят из аппроксимируемых задач. Класс RMAX(2) содержит полные в нем згА^чя, ь частности МАХ CLIQUE, которая не является аппроксимируемой, если NP ф Р. Оптк-мизациояные задачи, которые изучаются в главе 3, могут рассматриваться как кандидаты на задачи из класса RMAX(2), не полные в нем. по все еше не аппроксимируемые ни с какой постоянная точностью. (Точное доказательство этой гипотезы влекло бы доказательство утверждения NP =¡£ Р, что недостижимо сушествуюшнмн методами.) Отметим, что для любого к задача fc-CON сводится к (fc + 1)-C0N я к MAX|OSI>.„, задачи MAXi0S„.„, i-GON и ¿-CON сводятся к MAX CLIQUE, и никакие другие сводимости между этими задачами неизвестно.

В §4 главы 3 обсуждается вопрос о предполагаемой неполноте в классе Я.МАХ(2) задач fc-GON, иными словами, сводится sz MAX CLIQUE к к-GON. Рассматриваются некоторые естественные попытки такого сведения и показывается, что они не приводят к успеху.

Отметим, что задача MAX CLIQUE эквивалентна задаче нахождения размера наибольшего независимого множества в графе, которую мы обозначим IND SET. Возможное сведение IND SET к fc-CON могло бы

"М. Bellare. S. Goldwasser. С. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proc. ofikettth ACM Ann. Syrr.p. on the Theory of Computing (STOC), pages 294-304,19S3.

"C.H. Papaiiimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425-440,194.

13A. Panconesi and D. Ranjan. Quantifier» and approximation. Theoretical Computer Science, 107:145-163,1993.

заключаться в следующем. В графе G, размер наибольшего независимого множества в которой; следует определить, каждая вершина замещается i'-уголышком путем создания новой (к — 1)-й вершины. Ребро, которое входило в вершину графа G, может теперь входить в любую новую вершину соответствующего ¿-угольника. В случаях к = 2,3 сведение такого сорта является успешным при некотором ослабленном понятии сводимости. Однако, оказывается, что уже в случае к = 4 полученный таким образом граф может иметь слишком мнбго "лишних" независимых четырехугольников, которые содержались в G.

Теорема 4 Пусть /—произвольное сведение описанного вида. Тогда для полного двудольного графа Л'т-т справедливо opt то set{ Km,™) — m. но 0pi4-G0Jv(/(A*„,m)) >Щт2).

Рассматривается также еше один подход. Для заданного графа Н, граф G определяется следующим образом. Вершины G отождествляются с t-угольниками графа Н. Две вершины связаны в G ребром, если соответствующие t-угольнпкп зависимы. Граф G называется графом зависимости между к-угольпиками графа И. Можно было бы попытаться свести IND SET к t-GON, построив для графа G, являющегося входом >адачи IND SET, граф Н такой, что G был бы графом зависимости между t-угольниками графа Я. Оказывается, это невозможно, например в случае к = 4, ввиду следующего утверждения.

Теорема 5 Существует граф G, который не является графом зависимости между четырехугольниками ни для какого графа.

Автор выражает искреннюю признательность своим научным руководителям С.И.Адзау и А.А.Разборову.

Результаты гла» 2 и 3 получены при поддержке Фонда Джорджа Сороса.