Релятивизуемость в структурной теории сложности вычислений Верещагин, Николай Константинович

Введение к работе

Актуальность темы. Большинство теорем общей теории алгоритмов, как известно, реллтивизустся. Это значит, что для любого языка Л теорема останется верной, если в качестве модели вычисления взять машину Тьюринга с оракулом А. В полиномиальной теории алгоритмов это не так. В 1975 году в работе¹ были построены такие оракулы Л, В, что Г^л ф NP"⁴, Р^в = NP^/J. Хотя до сих пор неизвестно, какое из двух утверждений Р ф NP, Р = NP истинно, ни то ни другое утверждение не релятишізу-ется. После работы¹ было получено много результатов следующего вида: для некоторых пар сложностных классов, зависящих от оракула С, Яр, К%', доказывалось, что существуют оракулы Л и В, для которых I(f ф [{, Ку = К~2- Многие интересные классы лежат между Р н PSPACE, для таких классов в качестве второго оракула можно всегда брать оракул В из работы¹, потому что для него на самом деле верно Р^л = PSPACE^B.

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

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

'Т. Baker, J. Gill, ami R. Solovay. Krlativizntion of P=?NP question. SI AM Journal on Computing, 4(4):431-412, 1975.

^JC. Limrl, L. Fortiiovv, II. KailofT, nw! N. Nisan. The polynomial time hierarchy Ііая interactive proofs. In 31th Annual IEEE Symposium on Foundation oj Computer Science, pages 2-10, 1990.

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

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

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

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

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

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

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

VLi А'іЗЬг Є Ку. (Li сводится по Тыорннгу к Ь-_г), т.е., «Л'і сводится по Тыорннгу К Л^-2».

3) Построены оракулы, относительно которых UP Л Co-UP $2 ВРР, П. П Co-R g ФР, FewP Л Co-FewP UP, Co-R NP, AM Л co-AM $ PP. Вместе с ранее известными результатами это дает полное описание всех релятивизуемых включений между сложностннмп классами Р, NP, Co-NP, NPnCo-NP, R,Co-R, ІШСо-R, ВРР, UP, Co-UP, UPCCo-UP, FewP, Co-FewP, FewPnCo-FewP, Few, _fe, Il_fcl ЕьПГЦ, МЛ, Co-MA, МАпСо-МЛ, AM, co-AM, AM Пco-AM, IP, Co-IP. IP П Co-IP, фР, PP и PSPACE.

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

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

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

в) Для некоторого оракула А класс 1Р^Л Л Со-1Р^л не явля
ется II^л Л Со-11^л-полным относительно тыорннговоп
<у -сводимости.

г) Для некоторого оракула А класс Few не является
UP Л Со-UP^л-полным относительно тыорннговоп
-сводимости.

5) Доказано, что 3/1 IV Л Co-R^{л r}j^A фР^л, 3/1 UP'¹ Л Со-иР^л і'₇'.'^и ВРР'¹, ЗЛ FewP-⁴ Л Co-FewP* &/ UP'¹, ЗА \\^А 'j^A NP^A Л Со-ЫР^л, ЗЛ ВРР^Л &:^А NP'\ 3/1 ФР^Л 4^л 1Р^Л, ЗА Е^л Л П^л і$^л ]Р^А, ЗА АМ^Л Л со-АМ^л^'^лМА^л.

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

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

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

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

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

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

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