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

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

Мехг.нш;о-математический факультет

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

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

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

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

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

Москва—1994

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

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

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

Ведущее учреждгпие:

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

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

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

Защита диссертации состоится У " ¿-¿^С-Е^С-*-^" 2994 г_ в 16 час. 05 мин. на заседании специализированного Совета Д .053.05.05 при Московском государственном университете им. М.В.Ломоносова по адресу: 119399, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, ауд. 14-08.' '" ■

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

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

/А агсг^

1994 г.

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

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

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

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

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

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

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

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

'M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigdetson. Multi-prover interactive proofs: how to remove intractability assumption. In Pmc. of the 20¡A ACM Ann. Symp. on the Theory of Computing (STOC), pages 113-131, 1988.

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

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

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

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

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

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

Система (V,Pi,...,Pi) является мультииптерактивгой системой доказательств дли языка L (представляет му.штииите.рактивный протокол для L), если выполнены следующие условия.

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

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

Машины V, Pi,..., Pi мы называем -игроками V, Р\,..., Pi.

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

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

-Теорема 1 Д-.т некоторой константы с классы MIP -а 1Р('2. с) совпадают.

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

JL. Babai. L. Fortnow, and С. Lund. Non-deterministic exponential time has two-prom interactive protocols. Compvtational complexity, 1(1):3—40. 1991.

/

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

Все перечисленные работы исходят из наличия для любого языка L из класса МIP системы доказательств (У,р1,р2). ограничивающейся одним раундом, но имеющей вероятность ошиС::п 1 — 1/п£ {[2]). Далее зта система будет упоминаться как протокол П. Повторение протокола П последовитем'ко nc+1 раз позволяет уменьшить эту ошибку до экспоненциально малой величины (1 — l/ne)"e+1 ~ е-", однако требует возрастающего числа раундов. В перечисленных ьыше работах предложены различные способы преобразования исходного протокола П, уменьшающие вероятность ошибки без увеличения числа раундов.

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

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

3J. Kilian. Stiong separation models of multi-piovcr interactive proofs. DIM ACS Workshop on Cryptography, 1990.

4U. Feige. On the success probability of the two prover in one round proof systems. In Proc. of ike 6th Ann. Conference on Structure in Coinpiczilg Theory, pages 116-123, 1991.

!D. Lapidot and A. Shamir. Fully parallelized multi-prover protocol for N EXP-time. In Proc. of ike Zini IEEE Ann. Sgmp. on Foundations of Computer Science (FOCS), pages 13-18, 1991.

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

7U. Feige and L. Lovasz. Two-prover one-round proof systems: their power and their problems. In Proc. of the 24iЛ ACM Ann. Sjmp. on tie Theory of Computing (STOC), pages 733-744,1992.

честве своего сообщения (уь - - • вектор (/i(xt),..., h(xk)), где h — некоторая функция, или же он "хитрит", посыла* игроку V вектор (hi(ii,...,xt),...,hi!(xi,...,xic)). Для осуществления этой проверки игрок V случайным образом выбирает к из множества {1,...Д-} и посылает другому игроку Р2 сообщение хк. Получив от Рг ответ у, игрок V сравнивает ук с у, и если они не совпадают, то прекращает игру и выдает отрицательный ответ. Как легко видеть, "хитрость" игрока Р\ будет распознана с вероятностью по крайней мере Jmin»P(/'i(xt,...,a:t) £ (A(ri),...,M^t))], гДе вероятность берется по распределению вектора (хь..., ху). Чтобы увеличить эту вероятность и таким образом уменьшить вероятность ошибки, в [2], как и во всех предшествующих работах по мультшштерактивным доказательствам, использовалось последовательное и независимое повторение этого процесса / раз, где I — /(А:)—некоторый полипом, что требовало возрастающего количества раундов.

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

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

Изучаемая проблема имеет следующую теоретико-игровую постановку, которая приводится а §1. Рассматривается игра G двух участников. Пусть X, Y, S, Т—конечные множества, предикат на X х Y х 5 х Т. Пара (х,у) выбирается случайным образом аз множества Q С X х У. х посылается игроку. 1, а у—игроку 2. Игроки I и 2 выдают ответы /(х) € S и h(y) € Т в соответствии со своими стратегиями / : X —> 5 ss h : Y —► Т. Если ф(х,у,/(:z),h(y)) = 1, то оба игрока выигрывают; в противном случае они проигрывают. Цель игроков 1 и 2—сообща максимизировать вероятность выигрыша. Вероятность выигрыша для

оптимальных стратегий игроков обозначается ш(0'}. Таким образом,

-»(О = тахР м*. ,,/(*),*(»)) = 1].

J,h

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

Игра G" определяется как выполнение игры G параллельно п раз. Белее формально, набор ((xi,yi),... ,{ха,уп)) вы&крается случайным образом из Q". Игрокам 1 и 2 открываются векторы х — (х\,... и У — (йь-'чУп), соответственно. Они выдают ответы F(x) = (/i(r)v... ,/„(z)) и Н(у) = (fti(y)<-- - -hntt/))- Теперь игроки выигрывают в случае Д"=, Л(х), )) = 1, и

П .¿=1

Единственные известные сейчас сотношения между С) и u(G") следующие:

{ш{£7))п <м(0") < u(G).

Корректность параллельного выполнения протокола П вытекала бы из факта быстрого стремления ) к 0 при п -+ со. Однако, в [4] построен пример нетривиальной игры G. для которой uj(G2 ) — w(G). Вопрос о поведении величины G") при п. стремящемся к бесконечности, исследовался в работах [4,7]. Тем i:e менее, не было даже известно, существует ли для любой- игры G такое п, Что w((?n) < wfG)'(см." обсуждение 'а [7])г.

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

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

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

rH. Furstenberg and Y. Katznelson. Л density version of the Hales-Jewett theorem. Journal ¿'Analyse Mttkemaiiqvt, 57,1991.

ш(С) = шахР

Г.Н

обязательно присутствует в и:( г). Множество {го-(аi),____'w(a^)} назиза-

ется комбинаторной прямой в /1". Лемма 2 диссертации утверждает, что u{G") не превышает максимальной плотности подьшсгества множества Q", не содержащего комбинаторных прямых, которая, сак доказано в [8]. является бесконечно малой величиной при возрастающем параметре п.

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

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

2. Максимальное -число согласованных клак размера k (¿-CON), /: > 2. Задан: граф G на множестве вершин N = UjL,A';, где для каждого i множество N{ независимо в G (т.е. никакие две вершины из N{ не соединены ребром); N; = VjNij и все множества попарно различны. Найти: максимальное число клик размера к в G .таких, что для произвольных не более чем одна вершина из Njj принадлежит какой-либо из этих юшк. (Такпе клики названы согласованными.)

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

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

SP. Betro&ii and G. Schnitger—On the complexity of approximating the Independent

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

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

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

п) Если хотя бы одна из задач k-GON для к > 3 или k-CON для к > 2 аппроксимируема с точностью до множителя с > 1, то NP Ç DTIME(n°^).

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

iiii) Если задача MAX]ogn n аппроксимируема с точностью до множителя с> L, то MP = Р.

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

Set problem. In Proceedings of the STACS'89. Lecture Notes «я Computer Science, 349, pages 256-268, Springer-Verlag, Nor York/Berlin, 1989.

10u. Feige, S. Goldinsser, I. Lonsz, S. Safra, and M. Szegedy. Approximating clique is almost N P-complete. ia Fioc. of the 32 n¿ IEEE Ana. Symp. on Foundations of Computer Science (FOCS), pages 2-12, 1991.

• _ . . - ' : 8 . /■ V. • •

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

[И].

Утверждения теоремы 3 представляют интерес с точки зрения логической классификации оптимизационных NP-задач, предложенной в [12, 13]. Рассмотренные задачи MAXiogn.n, k-GON, ¿-CON попадают в класс RMAX(2) этой классификации (определения см. в Si). Класс RMAX(2) занимает в логической классификации особое место, тгз как классы, имеющие более простое логическое задание, состоят из аппроксимируемых задач. Класс R.MAX(2) содержит полные в кем задача, ь частности МАХ CLIQUE, которая не является аппроксимируемся, есля NP 4- Р- Оптимизационные задачи, которые изучаются в главе 3, могут рассматриваться как кандидаты на задачи из класса RMAX(2), ве полные в нем. г.о все еше не аппроксимируемые ни с какой постоянной точностью. (Точное доказательство этой гипотезы влекло бы доказательство утверждения NP ф Р, что недостижимо существующим методами.) Отметим, что для любого к задача fc-CON сводится с (к + 1)-CQN и к MAXiOÍ„,n-задачи MAXlos„,n, i-GON и к-CON сводятся к MAX CLIQUE, и никакие другие сводимости между этими задачами неиэветгяь:.

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

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

"М. Bellire, S. Goldwasser. С. Lund, and A. Russjü. Efficient probabilistically checkable proofs and applications to approximation.In Five. oflkclStk ACM Ann. Symp. on the Theory of Computing (STOC), pages 294-304,1903.

12C.H. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Compvter anil System Sciences, 43:425-440,1941.

13A. Panconesi and D. Ranjan. Quantifiers and approximation. Theoretical Competer Science, 107:145-163, 1993.

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

Теорема 4 Пусть /—произвольное сведение описанного вида. Тогда для полного двудольного графа Кт,т справедливо opt то set{ Кт.т) = т. но орЦ-соы(ЯКп,т)) > Щт2).

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

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

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

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