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

РГВ од

! ■ '

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА механико-математический факультет

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

ВЕРЕЩАГИН Николай Константинович

РЕЛЯТИВИЗУЕМОСТЬ В СТРУКТУРНОЙ ТЕОРИИ С Л О Ж НОСТИ В ЫЧИС Л ЕНИЙ

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

АВТОРЕФЕРАТ диссертации па соискание учёной степени доктора физико-математических наук

МОСКВА — 1995

Работа выполнена в Московском институте новых технологий образования.

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

доктор физико-математических наук доктор физико-математических наук доктор физико-математических наук, профессор

В. П. Оревков Л. А. Разборов

II. II. Редькнн

Ведущая организация — Казанский государственный университет

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

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

Защита состоится

года в 16

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

Д.053.05.05 при МГУ доктор физико-математических наук, профессор

Ученый секретарь диссертационного совета

/

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

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

Актуальность темы. Большинство теорем общей теории алгоритмов, как известно, релятнвизуется. Это значит, что для любого языка А теорема останется верной, если в качестве модели вычисления взять машину Тыорпнга с оракулом А. В полиномиальной теории алгоритмов это не так. В 1975 году в работе1 были построены такие оракулы Л, В, что Гл ф NP'1. Р/; = NP11. Хотя до сих пор неизвестно, какое из двух утверждений Р ф NP, Р = NP истинно, ни то ни другое утверждение не релятивпзу-ется. После работы1 было получено много результатов следующего вида: для некоторых нар сложностных классов, зависящих от оракула С, Яр, доказывалось, что существуют оракулы А и В, для которых I(f ф , Ztf = /\"¡¡!. Многие интересные классы лежат между Р и PSPACR, для таких классов в качестве второго оракула можно всегда брать оракул В из работы1, потому что для него на самом деле верно Pö = PSPACEß.

Первые нерелятивизуемые теоремы появились только в 1989 году, первая из них — теорема из работы2: РН С IP. Как было доказано ранее в работе3, существует оракул, относительно которого Р1Г IP- До спх пор неизвестны нерелятивизуемые доказательства различия каких-нибудь сложностных классов и вообще доказательства каких-нибудь отрицательных утверждении.

Построение оракулов, относительно которых выполнено то или иное утверждение о сложностных классах, скажем, оракуль-пое отделение классов, превратилось к настоящему времени в обширную область внутри структурной теории сложности вычислений. Подобного рода результаты имеют отрицательный характер: они показывают невозможность доказательства соответствующего утверждения с помощью релятиоизуемоп техники. Представляется естественным при появлении очередной

'Т. Baker, J. Gil!, ami R. Solovay. Hrlativization of P=?NP question. SI AM Journal on Computing, 4{4):43i-4A2, 1975.

SC. Limrl, L. Fortnovv, 1!. Kailotl, awl N. Nisan. The polynomial timo hierarchy lias interactive proofs. In 31th Annual JEEE Symposium on Foundation of Computer Science, pages 2-10, 1990.

3L, Fortnow and M. Sipser. Are there interactive protocols for coNP languages? Information Processing Letters, 28:2*19-251, 1988.

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

Цель работы. В диссертации исследуется релятивизованная сложность вычислений в следующих направлениях: доказываются общие теоремы о возможности релятивизуемого доказательства утверждений некоторого типа в структурной теории сложности вычислений (глава 1 и, частично, глава 4), доказываются конкретные теоремы о существовании оракулов, относительно которых имеет место то или иное соотношение между сложностными классами (главы 2, 3 и 4), исследуется взаимоотношение между сложностными классами относительно случайного оракула (глава. 5). Отдельная глава посвящена нижним оценкам сложности персептронов, тесно связанным с оракульным отделением различных классов от класса РР.

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

Научная новизна. Все результаты диссертации являются новыми. Основными результатами работы можно назвать следующие.

1) Общая схема определения сложностных классов

2) Критерии (в абсолютных терминах) возможности релятивизуемого доказательства утверждений следующих четырёх типов: Л' 1 С А'з; К-> имеет Л*1-трудную по Карпу проблему; содержит /^-трудную по Куку проблему;

VLi G A"i3Z/2 € Ky. (Li сводится no Тыорингу к L-¿), т.е., «Íí'i сводится по Тыорннгу к Л*2».

3) Построены оракулы, относительно которых UP П Co-UP $2 ВРР, П. П Co-R g фР, FewР П Co-FewP £ UP, Co-R ¿ NP, ЛМ П co-AM PP. Вместе с ранее известными результатами это дает полное описание всех релятивизуемых включений между сложностннмп классами Р, NP, Co-NP, NPnCo-NP, Е, Co-R, IinCo-R, ВРР, UP, Co-UP, UPHCo-UP, FewP, Co-FewP, FewPnCo-FewP, Few, £fe, Efennfc, МЛ, Co-MA, MA П Co-MA, AM, co-AM, AM П co-AM, IP, Co-IP. IP П Co-IP, фР, PP и I'SPACE.

'1) Пусть <j.'A обозначает полиномиальную Тыо|)ппгону сводимость, реллтпвнзованную оракулом А.

а) Доказано, что для некоторого оракула А класс 1РЛ П Со-1Рл не является ИРЛ П Co-UP^-полным относительно <j'A -сводимости.

б) Доказано, что для некоторого оракула А класс 1РЛ не является ВРРл-полпьш относительно <1¡:A-сводимости.

в) Для некоторого оракула А класс 1РЛ ПСо-1Рл не является IIл П Со-Вл-полным относительно тыорннговон

<5.'Л-СВОДИМОСТИ.

г) Для некоторого оракула А класс Ге\\'Л не является Ш,л П Со-Ш,л-полным относительно тыорннговон <J¡л -своди мости.

5) Доказано, что ЗА Ил П Со-11л ф1"\ 3/1 UP'1 П

Co-UPл £Г,Л ВРР'\ ЗА low!>л n Co-PewРл UP'1,

ЗА RA i'¡:A NP'1 п Со-ЫРл, ЗА ВРРЛ NP'1,

3/1 ФРЛ 1РЛ, ЗА Ел П 1РЛ, 3/1 АМЛ П

со-АМл МАЛ.

0) Построены оракулы, относительно которых выполнены различные булевы комбинации утверждений I' = NP, Р = R,

Р = ВРР, Р = NP П Co-NP, Р = R П Co-R, «любые дизъюнктные NP-множестпа Р-отделпмы» и «любые дизъюнктные Co-NP-множества Р-отделимы». Именно, построены оракулы для тех 13 из 17 возможных комбинаций, из которых не следует, что Р ф ВРР и любые дизъюнктные Co-NP-множества Р-отделимы (для двух комбинаций оракулы были известны ранее).

7) Доказано, что относительно случайного оракула существуют как Р-неотделнмые NP-множества, так и Р-неотдели-мые Со-ЫР-множества, и что относительно случайного оракула класс Co-NP содержит NP-нммунные множества, а класс NP содержит Co-NP-иммунные множества.

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть использованы в работах по структурной теории сложности вычислений.

Апробация работы. Результаты диссертации докладывались на семинарах кафедры математической логики и теории алгоритмов механико-математического факультета МГУ: семинаре под руководством С.И. Адяна и В.А. Успенского, семинаре под руководством С.И. Адяна и семинаре под руководством А.Л. Семенова, А.Х. Шеня и Н.К. Верещагина, на совместном семинаре по сложности вычислений МИАН и ВЦ РАН под руководством A.A. Разборова и C.B. Тарасова, на Вторых математических чтениях памяти М.Я. Суслина (Саратов, 1991) и на следующих международных конференциях: Седьмой конференции но структурной теории сложности вычислений (Бостон, 1992) (Structures'92), Конференции по логическим основаниям теории алгоритмов (Тверь. 1992) (Logic at Tver'9'2), Восьмой конференции по структурной теории сложности вычислений (Сап-Диего, 1993) (Structures'93), Школе по сложности, логике и теории алгоритмов (Амстердам, 1994) (COLORET Workshop'94), Третьем израильском симпозиуме по компьютерным системам и теории алгоритмов (Тель-Авив, 1995) (ISTCS'95).

Публикации. Результаты диссертации опубликованы в S работах, приведенных в конце автореферата. Все результаты, опубликованные в совместной работе [3J, получены независимо автором и С. Джейном и JI. Хемаспаандрой. В совместной работе [4] теорема о том, что относительно некоторого оракула NP-;множества и Co-NP-множества Р-отделимы, Р = ВРР, но Р ^ NP получена An. А. Мучником, а теорема о том, что относительно некоторого оракула NP-множества Р-отделимы, Co-NP-миожес-тва Р-неотделимы и Р = ВРР получена совместно Аи. А. Мучником и автором.

Структура и объем диссертации. Диссертация состоит из введения и пяти глав, разбитых в общей сложности на 15 параграфов. Нумерация теорем двойная — номер главы, номер теоремы. Общий объем диссертации — 139 страниц. Библиография содержит 48 наименований.

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

Глапа 1. Глава 1 посвящена общим теоремам о возможности ре-лятивнзуемого доказательства положительных утверждении некоторых типов о сложностных классах. Для того, чтобы можно было сформулнропать подобные теоремы, мы сначала определяем некоторую общую схему для определения сложностных классов, лежащих между Р и PSPACE.4 Общность этой схемы подтверждается тем, что все известные автору из литературы классы, лежащие между Р и PSPACE, могут быть естественным образом определены по этой схеме. Независимо эта же схема была найдена в работе5

Мы интересуемся критериями (в абсолютных терминах) возможности релятнпизуемого доказательства утверждений следу-

4Мы интересуемся сложности!,тми классе именно в этом диапазоне. Для пзпестпых классов пыше PSPACE (экспоненциальных и т.п.) или ниже Р (логарифмических и т.п.) существует аналогичная схема.

5D, P. Bovet, P. Crcs7.cn7.i, and П. Silvcstri. Л uniform approach to define complexity classes. Theoretical Computer Science, 104:263-283, 1992.

ющих четырёх типов, наиболее популярных в литературе:

к 1 С К2, (1)

Л'г имеет К\-трудную по Карпу проблему, (2)

К2 содержит A'i-трудную по Куку проблему, (3)

VLi G К\ЗЬ^ € К2 сводится по Тьюрингу к ¿2, (4)

т.е., «/v'i сводится по Тьюрингу к AV-

Что касается утверждений типа 2 и 3, обычно интересуются частным случаем этих утверждений —■ существованием полных проблем в сложностных классах. В контексте нашей работы представляется более естественным изучать именно существование в одном классе проблемы, трудной для другого класса.

Неформально, критерии состоят в следующем. Пусть К — некоторый сложностной класс. Обозначим через A'LOGS класс, полученный из класса К заменой всех полиномов, входящих в определение класса К, на полиномы от логарифма и заменой проблем разрешения (т.е. языков) на проблемы отделения. Тогда (1) выполнено относительно любого оракула тогда и только тогда, когда Л'!LOGS С A'oLOGS, а (2) выполнено относительно любого оракула тогда и только тогда, когда класс A^LOGS содержит язык, являющийся I\'i LOGS-трудным относительно некоторой сводимости. Анализ доказательств релятивизуемых утверждении типа (1) (например, ВРР С £2ППг из работы6) показывает, что более естественная формулировка этих утверждений имеет как раз вид AiLOGS С AILOGS. Такой же вид имеют и критерии истинности утверждений (3) и (4) относительно любого оракула.

Указанные четыре критерия сформулированы и доказаны в параграфах 1.2, L.3, 1.4 и 1.5 (соответственно теоремы 1.1, 1.4, 1.7 и 1.8). Теорема 1.1 придаёт новый смысл результатам об отделении сложностных классов с помощью оракулов: построение оракула, относительно которого Кj ф К?, доказывает различие (абсолютное: без оракулов) полилогарифмических аналогов классов A'i и AV

еМ. Sipser. A complexity theoretic approach for randomness. In ISlh Annual ACM Symposium on Theory oj Computing, pages 330-335, 1983

Теорема 1.1 имеет ещё и следующий смысл. Все известные конструкции оракулов, относительно которых какие-нибудь два сложностных класса Кi и К? различны (фактически доказывается, что Ki Кили наоборот) устроены следующим образом: имеется общая «диагональная» часть — построение оракула по шагам — и специфическая комбинаторная часть, обеспечивающая возможность выполнении каждого шага. Теорема 1.1 (точнее, та её иолошша, в которой утверждается, что iv'jLOGS 2 Л'з LOGS => ЗА h'f <£. К2 )> как Раз " заключает в себе общую диагональную часть всех таких доказательств. А специфическая комбинаторная часть заключается в доказательстве утверждения

KiLOGSg KjLOGS.

В литературе появлялись также теоремы, утверждающие существование оракула, для которого сложностные классы не содержат полной но Карпу (или по Куку) проблемы. Первой известной автору работой такого тина является работа', в которой доказано, что существует оракул, относительно которого класс NPnCo-NP не имеет полной но Карпу (т.е. относительно полиномиальной m-сводимостп, причём сводимость релятивизустся тем же оракулом) проблемы и такой оракул, относительно которого класс 11 не имеет полной по Карпу проблемы.

Все вышесказанное о построениях оракулов, относительно которых различаются сложностные классы, относится и к известным построениям оракулов, относительно которых сложностные классы не имеют полной проблемы. В частности, теорема \А заключает в себе общую диагональную часть таких построении.8

Глава 2. Новый взгляд на релятивизуемые теоремы четырех указанных видов, как на теоремы об абсолютных классах, делает психологически и технически более простым решение конкретных проблем типа (1)-(/1).

' М. Sipser. Oil relatjvizations anrl the existence of complete sets. International Colloquium on Automata, Languages anil Programming, 1982. Ltciurt Notes in Computer Science, 140:523-531, 1982

'Независимо, теоремы 1.1 и !.>! были доказаны п работе D. I3. Bovet, P. Cres7.eii7.i, and П. Silvestri. Л uniform approach to define complexity classes. Theoretical Computer Science, 101:263-283, 1992.

В главе 2 для многих известных из литературы классов К\, К2 между Р и PSPACE, к которым применимы критерии главы 1, выясняется, какое из двух утверждений — (1) или отрицание (1) — имеет место, или это неизвестно, и аналогично для утверждений типа (2), (3), (4). Мы выбрали для исследования следующие хорошо известные из литературы классы между Р и PSPACE: Р, NP, Co-NP, NP ПСо-NP, R, Co-R, RnCo-R, BPP, UP, Co-UP, UPnCo-UP, FewP, Co-FewP, FewPnCo-FewP, Few, Efc, Щ, Е*ПЩ, MA, Co-MA, МАПСо-МА, AM, co-AM, АМПсо-ЛМ, IP, Co-IP, IP П Co-IP, фР, PP и PSPACE.

Параграф '2.1 посвящен оракульному отделению этих слож-постных классов друг от друга. Известные релятнвнзуемые включения между этими классами указаны на Рис. 1.

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

1. ЗА UPA П Co-UP-4 g ВРРЛ 7. ЗА АМЛ П со-АМл g РРЛ ' 2. 3A.RA О Co-R"4 g фРл 8. ЗА АМЛ £ £л

3. ЗА Co-UP-4 g 1РЛ 9. ЗА РРЛ £ РНЛ

4. ЗА FewP-4 П Co-FewPA g иРл 10. ЗА фРл £ РНЛ

5. ЗА Co-R'4 g NP'4 П. ЗА фРл g РРЛ

6. ЗА 1РЛ П Со-1Рл g РНЛ 12. ЗА Пл g £л при к>Ъ

Из них следующие утверждения были известны ранее: Утверждение 3: ЗА Co-UP"4 g 1РЛ п0 существу доказано в работе9 (формально, там доказывается более слабое утверждение ЗА Co-NP4 g 1РЛ).

Утверждение G: 3/1 1РлПСо-1Рл g РНЛ но существу доказано в работе10. Именно, там доказано, что ЗА IP-4 g РНЛ. Сделав в доказательстве несущественные изменения, можно доказать, что существует такой оракул А, что 1РЛ ПСо-1Рл g РНЛ.

Fortnow and M. Sipser. Are there interactive protocols for coNP languages? Information Processing Letters, 28:249-251, I9SS

!0W. Aiello, S. Goklwasser, and J. Hâstad. On the power of interaction. In 27th Annual IEEE Symposium on Foundation of Computer Science, pages 368-379, New York, 1986. IEEE

Рис. 1. Релятнвизуемые включения сложностиых классов.

РЯРЛСЕ4

Утверждение 8: ЗА АМЛ $2 Ео1 доказано в работе11.

Утверждение 9: ЗА РРЛ ££ РНЛ легко следует из того, что функция MAJORITY^!,. .., хп) не представима в виде

\/ Л •■• V Л л.....-«to....,*»),

»1 = 1 >2 = 1 ¿21-1=1 <2t = l

гДе /¿i - bt (^-'1, • • •, £п) — это переменная или отрицание переменной, ни для какого фиксированного к 6 N (см. работу12).

Утверждение 10: 3/1 фРЛ g Р1!л доказано в работе13.

Утверждение 11: ЗА фРи (Z РРЛ легко следует из доказанного в работе13 утверждения о том, что функция PARITY от п переменных не вычисляется персептронами порядка меньше п. В указанном виде теорема впервые появилась в работе14.

Утверждение 12: Vfc > 3 ЗА П^ % Ej? следует из известных нижних оценок на размер Ел-схем, требуемых для вычисления Щ-функций, полученных Сипсером и другими. Необходимая нам оценка где f(n) растет быстрее любого полилогарифма,

была получена в работе15.

Таким образом, остаётся доказать утверждения 1, 2, 4, 5 и 7. В параграфе 2.1 доказаны утверждения 1, 2 и 5. Утверждение 4 доказано в параграфе 2.2, а доказательство утверждения 7 ввиду его сложности и интересной связи с персептронами выделено в отдельную главу.

В параграфе 2.2 мы выясняем, для каких пар классов A'i, K-j среди классов, показанных на Рис. 1, класс К\ сводится по Тьюрингу к классу А'2 относительно любого оракула. Известные ре-лятивизуемые утверждения о сводимости по Тыорингу показаны на Рис. 2

"М. Santha. Relativized Arthur-Merlin versus Merlin-Arthur games. Information and Computation, 80:44-49, 1989

,JJ. Hastad. Almost optimal lower bounds for small depth circuits. In 18th Annual ACM Symposium on Theory oj Computing, pages 6-20, 19S6

l3M. Minsky and S. Papert.. Perxeptrons. MIT Press, Cambridge, MA, 1988

MC. H. Bennet. and J. Gill. Relative to a random oracle P^NP^coNP with probability 1. Si AM Journal on Computing, 10:96-113, 1981

15J. Hastad. Almost optimal lower bounds for small depth circuits. In 18th Annual ACM Symposium on Theory oj Computing, pages 6-20, 19S6

Рис. 2. Тыориигопа сводимость сложностных классов

Мы не знаем, точен ли Рис. 2, т.е., все ли пары классов, сводящихся один к другому относительно любого оракула, указаны на рисунке. Чтобы доказать это, необходимо и достаточно доказать следующие 15 утверждений.

1. ЗЛ IIА П Со-Г1А ¿Р"4 ®РА.

2. ЗЛ 11РЛ ЛСо-иРА &л ВРРА.

3. 3.4 Ре\уРА П Со-Ре\уРл А 11РА.

4. ЗЛ Г!/4 ¿РТ'А NPA П Со-ИРл.

5. ЗЛ иРА ^'А1РАПСо-1РА

6. ЗЛ £л п £РтА 1РА.

7. ЗЛ ВРРЛ л ЫРА.

8. ЗЛ ©Рл £р7:л РНа.

9. ЗЛ АМЛ А ЕА П ПА.

10. ЗЛ АМЛ Псо-АМа £рт'л МАа.

11. ЗЛ ФРЛ 1РА.

12. ЗЛ £А £л ПП£ (к > 3).

13. ЗЛ РНА £РтА (к > 1).

14. ЗЛ 1РА ПСо-1РА £¡1А РРА.

15. ЗЛ ЕА ПП^ РРА.

Насколько известно автору, в литературе не появлялось результатов о существовании оракулов, относительно которых некоторый класс не сводится по Тьюрингу к другому классу. Однако многие утверждения подобного сорта являются простыми следствиями известных результатов об оракульном отделении классов. Например, утверждение 5 следует из того, что класс 1РЛ ПСо-1РА замкнут относительно <у.,л-сводимости и того, что ЗЛ иРА 2 Со-1РА. Подобным же образом можно получить утверждения 8, 9, 12 и 13. Остальные утверждения указанного списка уже не могут быть получены в качестве простых следствии известных результатов.

В диссертации доказаны утверждения 1-4, 6, 7, Юн 11. Верны ли утверждения 14 и 15, неизвестно.

В параграфе 2.3 мы выясняем, для каких пар классов К1 (из числа классов, показанных на Рис. 1), класс К\ содержит

/\Ч-трудную проблему (как по Карпу, так и по Тьюрингу) относительно любого оракула.

Все известные случаи релятивизуемого существования в одном классе проблемы, трудной для другого класса, получаются по следующим двум правилам:

класс К 2 содержит К ^-трудную проблему относительно сводимости (сводимости <£J, если существует класс КА из списка Рл, (k > 1), фРл, РРА, PSPACEa такой, что I<i С КА С ;

класс содержит Кf -трудную проблему относительно сводимости если существует класс КА из списка РА, ЕА, ПА (k > 1), ©Рл, РРД, PSPACEa такой, что КА <рт КА <?т .

Ранее были известны следующие утверждения о неполноте для исследуемых классов. Сипсером в работе16 доказано, что для некоторого оракула А класс 11л не имеет полного языка относительно сводимости <£;л, в работе17 доказано, что для некоторого оракула А класс NPA Л Co-NPA не имеет полного языка относительно сводимости , в работе18 доказано, что для некоторого оракула А класс ВРР"4 не имеет полного языка относительно сводимости , в работах19, 20, 21 эти два результата усилены до <у.'л-сводимости; в работе22 доказано, что для некоторого ора-

16М. Sipser. О n relativizations and the existence of complete sets. International Colloquium on Automata, Languages and Programming, 1982. Lecture Notes in Computer Science, 140:523-531, 1982

17M. Sipser. On relativizations and the existence of complete sets. International Colloquium on Automata, Languages and Programming, 19SS. Lecture Notes in Computer Science, 140:523-531,1982

1SJ. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 58:129-142, 1988. Preliminary version appeared in: "International Colloquium on Automata, Languages and Programming", 1986. Lecture Notes in Computer Science, 19S6, Vol. 226, pp. 123-135.)

Ambos-Spies. A note on complete problems for complexity classes. Information Processing Letters, 23:227-230, 1986

20Y. Gurevich. Algeb

ras of feasible functions. In 24th Annual IEEE Symposium on Foundation oj Computer Science, pages 210—214, 1983

21J. Hartmanis and N. Immerman. On complete problems for NPucoNP. International Colloquium on Automata, Languages and Programming, 1985. Lecture Notes in Computer Science, 191:250-259,1985

22J. Hartmanis and L. Hemachandra. Complexity classes without machines:

кула класс UP/l не имеет полного языка относительно сводимости <£;л.

Мы не знаем, все лп случаи релятнвиэуемого существова-нпя в одном классе проблем, трудных для другого класса (среди рассматриваемых классов), получаются но указанным правилам. Чтобы доказать это, необходимо и достаточно доказать следующие 9 утверждении. Мы будем говорить, что класс К\ является А'г-нолным о тносительно сводимости <, если К\ содержит проблему, являющуюся Л'г-труднон относительно сводимости <.

]. Для некоторого оракула Л класс 1РЛ не является ВРРЛ-полным относительно сводимости <ТуА.

2. Для некоторого оракула А класс 1РЛ ПСо-1Рл не является Пл П Со-Т{л-полным относительно сводимости <у'Л.

3. Для некоторого оракула А класс 1РЛ ПСо-1Рл не является UP'1 П Со-иР/1-нолпым относительно сводимости <j'A.

4. Для некоторого оракула А класс Ре\ул не является UP/1 П Со-иРл-полным относительно сводимости <уА ■

5. Для некоторого оракула А класс РРЛ не является 1РЛ П • Со-1Рл-иолным относительно сводимости •

.. f 6. Для некоторого оракула А класс Ел не является Ел+, П

' 11л+1-нолным относительно сводимости <рА .

7. Для некоторого оракула А класс £л П 11л не является Ел П Пл-полным относительно сводимости <уЛ (к > 3).

8. Для некоторого оракула А класс Е2ПП2 не является ВРР -полным относительно сводимости <Ç'A ■

9. Для некоторого орйкула А класс £лЛПл не является FeW4-иолным относительно сводимости <j'A •

В главе 2 мы доказываем утверждении 1-4 (Следствием утверждения 2 является решение поставленной в работе23 проблемы су-

Ом complete languages for UP. Theoretical Computer Science, 58:129-142, 1988. , Preliminary version appeared in: "International Colloquium on Automata, Languages and Programming", 19S6. Lecture Notes in Computer Science, 1986, •Vol. 226, pp. 123-135.)

23M. Sipser. On relativixations and the existence of complete sets. International Colloquium on Automata, Languages and Programming, 19SE. Lecture Notes in Computer Science, 140:523-531, 1982

ществования оракула, относительно которого класс R не имеет полной по Тьюрингу проблемы). Утверждения 2 и 4 доказаны независимо автором и С. Джейном и JI. Хемаспаандрой, Верны ли утверждения 5-9, неизвестно. Интересно, что утверждения 2 и 3 можно легко вывести из теоремы 1.7 и известных результатов о булевских разрешающих деревьях из работы24.

Глава 3. Наиболее сложный из полученных нами конкретный результат об оракулыюм отделении сложностных классов состоит в построении оракула, относительно которого класс АМН со-A M не включён в класс PP. Доказательство этого результата основано на нижних оценках для персептронов, интересных и самих по себе,

Персептроном называется схема глубины 2 с пороговой вершиной в корне (т.е., вершиной, помеченной некоторым целым числом, называемым её порогом) и с вершинами, помеченными конъюнкциями (И-вершииами), на втором уровне. Каждый вход пороговой вершины помечен целым числом (возможно отрицательным), называемым его весом. Входами И-вершин являются булевские переменные и их отрицания. Персептрон выдаёт единицу, если сумма весов всех истинных входов корневой вершины больше её порога, и выдаёт 0 иначе.

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

Персептроны изучались Минским и Пейпертом в монографии i5. Среди результатов, полученных ими, нам хотелось бы выделить две теоремы о нижних оценках порядка персептронов, вычисляющих некоторые булевы функции. Первая гласит, что персептрон, вычисляющий сумму п булевских переменных по модулю 2 должен иметь порядок по крайней мере п. Вторая теорема утверждает, что персептрон, распознающий, все ли ряды

24R. Impagliazzo and M. Naor. Decision trees and downward closures. In Third Annual Conference on Structure in Complexity Theory, pages 29-38, 1988

25M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1988. (Expanded edition, first edition appeared in 1967.)

данной булевой матрицы размера п х An2 содержат по крайней мере одну единицу, имеет порядок не меньше п (теорема «один в блок?»). Бигел в работе26 построил булеву функцию п переменных, вычислимую некоторым персептроном экспоненциального (от п) общего веса и порядка 1, но не вычислимую иерсептронами квазиполииомнального

(2Poiy<iog(.i))) общего

веса и полилогарифмического (poly(log(»i))) порядка. Точнее, он получил нижнюю оценку d ' log it! — Î2(»i) на порядок d и общий вес w нерсентронов, вычисляющих эту функцию.

Мы развиваем теорему «один в блоке» Минского и ПеГшерта в следующем направлении. Пусть II обозначает следующую проблему отделения: отделить булевы матрицы, в которых каждый ряд содержит по крайней мере одну единицу, от булевых матриц, в которых много рядов (скажем, 99%) содержат одни нули. Очевидно, любой лерсентрол, решающим II, также распознаёт, содержит ли данная булева матрица 1 в каждом ряду. Мы доказываем, что проблему 11 невозможно решить, используя персен-, троны порядка о(^/т) и общего веса 2°'"), где п — это количество /* " рядов, a m — это количество столбцов матрицы (теорема 3.2). Из j этого следует, что персептроны нолилогарифмического порядка и квазиполииомнального общего веса не могут решить проблемы П.

Необходимость доказывания, что персептроны полилогарифмического порядка и квазиполииомнального общего веса не могут решать те или иные проблемы, часто возникает но следующей причине. При переходе от обычных недетерминированных машин с оракулом к схемам из функциональных элементов в стиле Фёрста, Сэйкса и Сипсера27, полиномиальные по времени машины соответствуют схемам глубины 2 квазиполииомнального общего веса и нолилогарифмического порядка, с вершиной, помеченной ИЛИ, в корне (булевскими переменными явля-

■ .. ются значения оракула на словах не более определенной длины). *

. 26 R. Bcigcl. Perceptions, PI3, and the polynomial time hierarchy. In Seventh Annual Conjercncc on Structure in Complexity Theory, pages 14-19, Boston, MA, July 1992

27N. FursI, J. Saxc, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Mathematical Systems Theory, 17:13-27, 1984

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

Таким образом, из теоремы Минского и Пейперта о порядке персептронов, вычисляющих функцию сложения по модулю 2, следует существование оракула, относительно которого ©Р £ PP. А из теоремы «один в блоке» следует, что NPnp g РР относительно некоторого оракула (см. работу28). Приведенный выше результат Бнгела показывает, что PNP §£ РР относительно некоторого оракула29. А наш результат о проблеме отделения П даёт оракул, относительно которого AM £ PP. Небольшое усиление этого результата показывает, что существует оракул, относительно которого AM П со-АМ g PP.

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

28В. Fu. Separating РН from РР by relativisation. Preprint, 1990

J9R. Beigel. Perceptions, PP, and the polynomial time hierarchy. In Seventh Annual Conjerence on Structure in Complexity Theory, pages 14-19, Boston, MA, July 1992

телыю которого сущсстпуют неотделимые Co-NP71-множества и неотделимые Ш>л-мпожсства н нрн этом Р = ВРР.

Необходимость построения подобных оракулов возникает по следующей причине. Когда было осознано, что скорее всего Р ф NP, по это трудно доказать (и невозможно доказать, используя только.релятпвпзуемую технику), появились интересные результаты н предположении, что Р ф NP. Важные проблемы подобного сорта возникают в криптографии, где надёжность всех известных протоколов обосновывается при предположениях даже более сильных, чем Р ф NP. Важной проблемой является построение криптографических протоколов, надежность которых можно доказать в предположении, что Р ф NP. В главе 4 мы устанавливаем, что многие теоретико-сложностные утверждения не могут быть доказаны с помощью релятивизуемой техники даже в предположении, что Р ф NP, и более сильных предположениях. Другими словами, ми строим оракулы, относительно которых выполнены различные булевские комбинации утверждения Р ф NP и других утверждении. Мы развиваем довольно мощный метод построения таких оракулов, а в последнем параграфе исследуем границы применимости метода. А именно, мы доказываем, что метод не годится для доказательства некоторых двух известных теорем.

В литературе имеется много результатов подобного рода (когда. строится оракул, относительно которого выполнена определённая булева комбинация теоретико-сложиостных утверждении). Среди них следующие результаты относятся к классам, изучающимся п диссертации. Ракофф в работе30 построил оракулы An В такие, что Рл = 11л ф NI"4 и Pß ф 11° = NPß. В работе31 было доказано, что Р = NPnGo-NP ф NP относительно некоторого оракула.

В главе 4 мы, к примеру, доказываем, существует оракул, относительно которого Р ф NP и любые дизъюнктные NP-множес-тва отделимы, решая таким образом проблему, оставленную не-

30С. RaokolT. Relativized «niestinns involving probabilistic algorithms. In 10th Annual ACM Symposium on Theory of Computing, pages 338-3)2, 197S

31T. Baker, J. Gill, and R. Solovay. Rclativization of P=?NP question. SI AM Journal on Computing, 4(4 ):43l -'142, 1975.

решённой в работе32 (независимо это было доказано в работе33), йз этого следует, что надёжность всех криптографических протоколов, основанных на существовании односторонних функций, не может быть обоснована с помощью релятивнзуемой техники в предположении, что Р ф NP (поскольку односторонние функции не существуют, если любые дизъюнктные NP-множества отделимы, см. работу34). Более того, мы показываем, что существование неотделимых NP-множеств не может быть доказано с помощью релятивнзуемой техники даже в предположении того, что существуют неотделимые Co-NP-множества и Р ф R.

Используемый нами метод восходит к работе35. Мы называем его «методом универсумов». Мы уточняем этот метод и применяем его к доказательству существования оракулов, относительно которых выполнены всевозможные булевы комбинации утверждений Р = NP, Р = R, Р = ВРР, Р = NP П Co-NP, Р = RH Co-R, «любые дизъюнктные NP-множества Р-отдели-мы» и «любые дизъюнктные Co-NP-множества Р-отделимы». Нам удалось построить оракулы для 13 из 17 возможных комбинаций (для двух из них оракулы были известны ранее); таким образом, четыре проблемы остаются нерешёнными.

Полученные результаты указаны в таблице 1.

Грубо говоря, метод работает следующим образом. Пусть мы, скажем, хотим доказать существование оракула, относительно которого Р ф ВРР, но Р = R. Для этого сначала нужно определить подмножество V множества всех оракулов (называемое универсумом). Во-вторых, нужно выбрать достаточно сильный и «правильно устроенный» оракул Н (во всех известных применениях в качестве Н годится любой PSPACE-полный оракул). В-третьих, вместо обыкновенных машин с оракулом следует рассматривать машины с двумя оракулами: оракулом Н и перемен-

32J. Grollman and A. L. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309~335, 19S3.

33L. Fortnow and J. Rogers. Separability and one-way functions. Manuscript, 1994

J. Grollman and A. L. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309-335, 19SS

35T. Baker, J. Gill, and R. Solovay. Relativization of P=?NP question. SJAM Journal on Computing, 4(4):431-442, 1975

Таблица 1. Знак «+< п строчке таблицы, означает, что соотпстствую-щее утверждение нстпино, а знак *—» — что соответствующее утверждение ложно. Знак »11» п последнем столбце означает, что оракул, относительно которого имеет место соотнстстпующая комбинация, был известен. Знак >Д» п последнем столбце означает, что оракул, относительно которого имеет место соответствующая комбинация, построен о диссертации. Знак «?• 5 последнем столбце означает, что неизвестно, существует ли оракул, относительно которого имеет место соответствующая комбинация.

N1'- Со-Ш>- Р =ИР ПСо-ИР Р = И ПСо-П

Р = ИР мн-ва отдел. мп-ва отдел. Р = ВРР Р = И

1 4 4 4 4 4 4 4 И

2 - 4 4 4 4 4 4 Д

3 - 4 4 + - 4 4 7

4 - 4 4 4 - - 4 V

5 - 4 - 4 4 4 4 д

0 - 4 - 4 - 4 4 д

7 - 4 - 4 - - 4 д

8 - - 4 4 4 4 4 д

9 - - 4 4 - 4 4 •7

10 - - 4 4 - - 4 ?

11 - - - 4 4 4 4 д

12 - - - 4 - 4 4 д

13 — - — 4 4 - 4 д

14 - - - - 4 4 4 д

15 - - — — - 4 4 д

16 — - — - — - 4 д

17 - - - - - - - 11

ным оракулом В, пробегающим множество V. (Таким образом, каждая машина этого типа допускает некоторое подмножество множества В* х V, где В = {0,1} — это входной алфавит.) Наконец, нужно доказать, что некоторая В РР-машин а этого типа распознаёт подмножество В* х V, не распознаваемый никакой Р-машнной этого типа, и что для любой Я-машины этого типа существует Р-машина этого типа, распознающая то же подмножество В* х V.

Общий метод, похожий на наш, был предложен в работе Фен-нера, Фортноу, Куртца и Ли36. Обобщение этого метода было использовано в работе Фортноу и Роджерса37 для построения оракулов, относительно которых выполнены всевозможные булевы комбинации утверждений Р = Р = 11Р, Р = ИРПСо-ОТ, «любые дизъюнктные НР-множества Р-отделпмы» и «любые дизъюнктные Со-ИР-множества Р-отделпмы». Авторам указанной работы удалось построить оракулы для всех возможных комбинаций.

В некотором смысле наш метод является частным случаем использования форсинга. В параграфе 4.3, мы формализуем метод универсумов и доказываем две общие теоремы о нём. Это делает возможным сформулировать, что означает что метод не может быть применён к доказательству того или иного утверждения. В параграфе 4.4 мы приводим две теоремы, которые не могут быть доказаны методом универсумов, это — теорема из работы38 о том, что Р ф И. = РБРАСЕ относительно некоторого оракула, и теорема из работы39 о том, что Р = № ф РБРАСЕ относительно некоторого оракула.

36S. Fermer, L. Fortnow, S. A. Kurtz, L. Li. An oracle builder's toolkit. In Eight Annual Conjerence on Structure in Complexity Theory, pages 120-131, May 1993

?,7L. Fortnow and J. Rogers. Separability and one-way functions. Manuscript, 1994

38C. Rackoff. Relativized questions involving probabilistic algorithms. In 10th Annual ACM Symposium on Theory of Computing, pages 338-342, 1978

39K.-I. Ko. Relativised polynomial-time hierarchies having exactly k levels. S1AM Journal on Computing, 18{2):392-40S, 1989

Глава 5. Поскольку соотношение между классами Co-NP4, NP"4 н Рл зависит от оракула А, естественно спросить, что имеет место относительно «типичного» оракула. Одним из возможных уточнений понятия тнннчностп является понятие генеричности в бэровской топологии. Другим возможным уточнением является понятие случайности по равномерной мере. В главе 5 мы изучаем соотношение классов NPA, Со-Ш>л и Рл для оракула А, случайного но равномерной мере. Точнее, мы говорим, что некоторое утверждение 5(/1) выполнено для случайного оракула, или для почти всех оракулов, если равномерная мера множества {/1 | 5(/1)} равна ]. Все интересующие нас утверждения S обладают следующими двумя свойствами: множество {Л | 5'(Л)} измеримо и Я(А) устойчиво относительно конечных изменений А. По 0-1-эакопу Л.II. Колмогорова, для всех таких свойств, либо 5(/1) выполнено для случайного А, либо -<S{A) выполнено для случайного /1.

Изучение соотношений между рассматриваемыми классами относительно случайного орд кула было начато в работе40, где было доказано, что РА ф NPA ф Со-М'л для случайного А. Там же было доказано, что для случайного А существуют Рл-иммунные Ш^'-множеетпа, т.е., бесконечные ИР^-множества, не имеющие бесконечных Рл-подмпожеств.

Посмотрим на отп результаты с точки зрения аналогии между качественной теорией алгоритмов и теорией сложности вычислений (количественной теорией алгоритмов). По зтой аналогии, множества из класса Р соответствуют разрешимым множествам, множества из класса NP соответствуют перечнелимым множествам, а множества из класса Co-NP соответствуют дополнениям перечнелимых множеств, т.е., консречислимым множествам. Точнее, мы рассматриваем аналогию между качественной теорией алгоритмов и теорией сложности вычислений, «релятп-внзованной случайным оракулом». В нашем случае разрешимым множествам соотнетгтпуют Рл-множества, иеречнелнмым множествам соответствуют Ш)Л-множества и консречислимым мно-

40С. Н. Beimel and .1. Gill. Relative to a random oracle P^NPjieoNP with probability SLAM Journal on Computing, 10:96-113, 1981

жествам соответствуют Со-ИР^-множества, где А — «случайный оракул». Таким образом, аналоги следующих двух теорем качественной теории алгоритмов верны в теории сложности вычислений относительно случайного оракула: аналог теоремы о существовании перечислимого неразрешимого множества и аналог теоремы о существовании коперечислимого неперечислимого множества. А аналог теоремы о том, что любое бесконечное перечислимое множество имеет бесконечное разрешимое подмножество неверен.

В главе 5 мы исследуем аналоги следующих трёх теорем теории алгоритмов:

1) теоремы о существовании перечислимых неотделимых множеств,

2) теоремы о существовании простого множества (перечислимого множества, дополнение которого бесконечно, но не имеет бесконечных перечнслимых подмножеств) и

3) теоремы об отделимости коперечислимых множеств.

Мы устанавливаем, что относительно случайного оракула, аналоги первых двух теорем верны, а аналог третьей теоремы неверен. Т.е., мы доказываем, что относительно случайного оракула существуют как Р-неотделимые NP-множества, так и Р-неотделимые Co-NP-множества, и что относительно случайного оракула класс Co-NP содержит NP-иммунные множества.

Кроме того, мы усиливаем теорему из работы41, утверждающую, что относительно случайного оракула существуют Р-иммунные NP-мпожества: мы доказываем, что, более того, относительно случайного оракула существуют Co-NP-иммунные NP-множества.

Остаётся открытой проблема, верен ли аналог теоремы Поста о разрешимости перечнслимых и одновременно коперечислимых множеств, т.е., неизвестно, верно ли, что NP^flCo-NP"4 = Рл для случайного А. Как замечено в работе42, если NP^flCo-NP"4 = Рл

""С. Н. Beimel and J. Gill. Relative to a random oracle P?SNP^coNP with probability ]. S1AM Journal on Computing, 10:96-113, 1981

42M. Blum and R. Impagliazzo. General oracle and oracle classes. In 2Sth Annual IEEE Symposiurn on Foundation oj Computer Science, pages 11S-12G, New York, May 1987.

для случайного А, п о AM Псо-ЛМ = J3PP, в частности, проблема изоморфизма графов принадлежит ВРР. Таким образом, мало надежд на то, что NP/l П Co-NP4 = РЛ для случайного А. .Никаких абсолютных следствии утверждения «NP4 П Co-NP^ ф Рд для случайного А» неизвестно, таким образом остаётся надежда доказать, что NP'1 П Co-NP4 ф Рл для случайного А.

Благодарности Автор благодарен Ли.А. Мучнику, А.А. Раз-борову, 10.11. Тюрину, J1. Хемаснаандре и А.Х. Шеню, беседы с которыми существенно повлияли на содержание результатов диссертации, а также 13.D. Борисенко и К.Ю. Горбунову за техническую помощь.

Публикации по теме диссертации

[1] II. К. Верещагин. Релятивизуемые и нерелятивнзуемые теоремы полиномиальной теории алгоритмов. Известия РАН. Серия математическая, 57(2):51-90, 1993.

[2] II. К. Верещагин. "Соотношение NP- и Co-NP-множеств относительно случайного оракула", Известия Высших Учебных Заведении. Серия Математика, 1993, N. 3, С. 31-39. Предварительные варианты в: Proc. of 8th Annual IEEE Conference on Structure in Complexity Theory, May 1993, San-Diego CA, pp. 132-138 и в: Вторые математические чтения памяти М.Я. Суслина, тезисы докладов (Саратов, 1991), стр. 13.

[3] L. Hemaspaanch a. S. Jain, and N. Vcreshchagiii. Banishing robust. turing completeness. International Journal on Foundations of Computer Science, 4(3):245-265, 1993. Предварительный вариант в: Logic at TVER '92, Symposium on Logical Foundations of Computer Sacncc. Lecture Notes in Computer Science, 1992, vol. 620, pp. 18(5-197.

[4] A. A. Muchnik and N. K. Vereshchagin. A general method to construct oracles realizing given relationships between complexity classes. Technical Report 500, Computer Science Department,

University of Rochester, 1994. (Принято к публикации в журнале Theoretical Computer Science.)

[5] N. К. Vereshchagin. On the power of PP. In 7th Conference on Structure in Complexity Theory, pages 138-143, 1992.

[6] N. K. Vereshchagin. Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP. In Third Israel Symposium on Theory of Computing and Systems, pages 46-51, 1995.

[7] N. K. Vereshchagin. Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP. Technical Report 498, Computer Science Department, University of Rochester, 1994.

[8] N. K. Vereshchagin. NP-sets are Co-NP-immune relative to a random oracle. In Third Israel Symposium on Theory of Computing and Systems, pages 40-45, 1995.