Вычислительная сложность некоторых задач математической логики

Дудаков, Сергей Михайлович

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

Дудаков, Сергей Михайлович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Тверь МЕСТО ЗАЩИТЫ

2000 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Вычислительная сложность некоторых задач математической логики»

Автореферат диссертации на тему "Вычислительная сложность некоторых задач математической логики"

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

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

РГ5 ОД

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

Дудаков Сергей Михайлович

Вычислительная сложность некоторых задач математической логики

Специальность 01.01.06 — «Математическая логика, алгебра и теория чисел»

Автореферат

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

Москва - 2000

С-От

Диссертация выполнена на кафедре информатики Тверского государственного университета.

Научный руководитель — кандидат физико-математических наук, доцент Дехтярь Михаил Иосифович.

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

доктор физико-математических наук, профессор Н.К.Верещагин

кандидат физико-математических наук М.К.Валиев

Ведущая организация:

Институт программных систем РАН

Защита диссертации состоится «. /9 » мал 2000 г. в

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

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

Автореферат разослан « I П » 0( И. _ 2000 г.

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

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

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

Актуальность

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

Линейная логика, которая является расширением классической, содержит внутри себя средства описания ресурсов, «запас» которых ограничен. Как и в классической логике, важной частью линейной логики является ее хорновский фрагмент с использованием мультипликативных связок, прежде всего, потому что он имеет прозрачную ресурсную семантику: хорновские импликации линейной логики можно рассматривать как некоторые преобразования (операции обмена) ресурсов, а доказуемость секвенции с их использованием — как возможность полностью осуществить все эти преобразования. Поскольку выводимость в хорновском фрагменте линейной логики является NP-пoлнoй задачей, то встает вопрос отыскания интересных (достаточно естественных) частных случаев, когда она может быть решена за полиномиальное время. Одним из наиболее естественных способов является «распараллеливание» вывода за счет использования как можно большего количества импликаций за один шаг. Оценкам эффективности такого распараллеливания посвящена глава 2 данной диссертации.

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

Еще одна важная задача, связанная с логическими программами, — это построение их моделей с заранее определенными свойствами. Как известно, логическая программа может иметь несколько моделей, поэтому часто возникает задача сужения множества моделей, а в идеале — выбора одной из них, опираясь на какие-либо естественные свойства. Одним из способов решения этой проблемы может быть использование совершенных моделей, которые предложены в 1988 году Пжимусинским. Недостатком этого приема является то, что не всякая логическая программа имеет совершенную модель. Поэтому возникает задача: определить по заданной логической программе существует ли у нее совершенная модель. Мы даем точную оценку сложности этой задачи и отвечаем на отрытый вопрос одной из работ Айтера и Готтлоба.

Наличие большого числа сложно решаемых задач и нерешенность проблемы эквивалентности детерминированных и недетерминированных вычислений подтолкнули к исследованию внутренней структуры полных задач. Появился целый раздел теории алгоритмов — структурная теория сложности, — посвященный именно этим вопросам. Прежде всего, это относится к их плотности и алгоритмической сложности, поскольку, например, при небольшой алгоритмической сложности задачи имеется практически значимый способ ее решения на начальном отрезке с использованием ограниченных ресурсов. В главе 5 мы исследуем сложность начальных отрезков NP-тpyдныx и ЕХР-трудных задач.

Цели работы

1. Определить точную оценку сложности задач, связанных с перестановочностью и параллельностью последовательностей хорновских импликаций. Найти новые классы последовательностей хорновских импликаций, для которых проблема выводимости была бы разрешима за полиномиальное время.

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

дель.

3. Исследовать сложность построения совершенных моделей пропозициональных нормальных логических программ и задачи выводимости в совершенных моделях.

4. Исследовать оценки информационной сложности начальных отрезков полных и трудных по Тьюрингу множеств для классов NP и ЕХР.

Методы исследования

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

Научная новизна и основные положения, выносимые на защиту

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

1. Установлены точные оценки сложности задач распознавания и применимости для классов перестановочных и параллельных последовательностей хорновских импликаций. Введены новые классы последовательностей: сильно параллельных, /¡-максимально параллельных и максимально параллельных. Для них также получены оценки сложности задач распознавания и применимости, и установлены соотношения между всеми этими классами.

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

3. Установлена структура совершенной модели логической программы. На основании этого предложен алгоритм, строящий совершенную

модель за полиномиальное время с NP-полным оракулом. Тем самым дан ответ на открытый вопрос работы Айтера и Готтлоба. Для установления точной оценки сложности введен новый класс D2 и показано, что задачи "PÍ7?..?-"-сов местности и T'í 7?. ^-следования являются D2 и соЮ2-полными соответственно.

4. Для NP-трудных по Тьюрингу множеств получена нижняя оценка информационной сложности начальных отрезков, чем дан ответ на открытый вопрос работы Дехтяря. Получено усиление теоремы Бука и Лютца о множествах с высокой информационной сложностью. В частности, предложен алгоритм построения начальных отрезков множеств, требующий экспоненциального времени.

Теоретическая и практическая ценность

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

Апробация работы

Содержание второй главы работы докладывалось на международной конференции по математическим основаниям информатики LFCS'97 [1], третей — на международной конференции по логическому программированию и немонотонному выводу LPNMR'99 [4]. В статье [4] автору принадлежат теоремы о сложности рассматриваемых задач. Содержание главы 4 о совершенных моделях логических программ было опубликовано в журнале «Fundamenta Informaticae» [3]. Содержание пятой главы исследования было опубликовано в виде тезисов на конференции «Мальцевские чтения», посвященной 90-летию со дня рождения А.И.Мальцева [2].

Результаты, изложенные в диссертации неоднократно докладывались на семинаре по компьютерной логике ТвГУ. Содержание диссертации также было представлено на семинаре МГУ по математической логике.

Структура диссертации

Диссертация содержит 139 страниц и состоит из введения, пяти глав основной части, заключения и списка литературы.

Краткое содержание работы

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

Глава 2: сложность параллельности для хорновского фрагмента линейной логики

Пусть S — это некоторое множество символов (алфавит). Мультипликативная конъюнкция (в дальнейшем — конъюнкция) — это коммутативное слово ai...ап, где ау,... ,ап £ S. Хорновская мультипликативная импликация (в дальнейшем — импликация) — это формула вида (а —» /?), где а и ¡3 — конъюнкции. Импликация (а -> /3) применима к конъюнкции w, если w — аи для некоторой конъюнкции и. Результатом применения называется конъюнкция w' = flu. Будем записывать это в виде w(a —> /3) Ь w'. Пусть Г = 7i ■••7n — последовательность импликаций. Г применима к конъюнкции w, если существуют (ii,...,in) ~ перестановка (1,..., п) — и последовательность конъюнкций wq = w, w\,..., uin такие, что 7j. I- Wj, j = l,...,n. Результат применения Г к w — w' = wn (wT h w'). Например, abc(ab —»• aab)(bc —> c) h aac, потому что abc(ab —)■ aab) h aabc и aabc(bc —» с) b- aac.

Известно1, что определение применимости последовательности импликаций к конъюнкции является NP-полной задачей, даже если алфавит состоит из двух символов. В работе Архангельского и др.2 предложены

1Kanovich M.I. Horn Programming in Linear Logic is NP-complete: Proc.7-th Annual IEEE Symposium on Logic in Computer Science — 1992 — pp. 200-210. Archangelsky D.A., Taitslin M.A. Linear Logic With Fixed Resources. // Annals of Pure and Applied Logic, v. 67 — 1994 — pp. 3-28.

2Archangelsky D.A., Dekhtyar M.I., Kruglov E., Musikaev I.Kh., Taitslin M.A. Concurrency problem for Horn fragment of Girard's Linear Logic: Logical Foundation of Computer Science, St.Petersburg'94, Lecture Notes in Computer Science, .№ 813 — 1994 — pp. 18-22.

классы перестановочных и параллельных последовательностей.

Последовательность импликаций Г = 71 ... 7П называется перестановочной на конъюнкции w, к которой Г применима, если п = 1 или для любого г = 1,... ,п такого, что wji Y- w' последовательность Г' = 7i... 7j_i7,+i ... 7„ перестановочна на w'. Интуитивно это означает, что на каждом шаге можно использовать любую применимую импликацию. Например, последовательность (а а2)(а2 а) перестановочна на а2, а последовательность (а2 —> а2)(а2 —> а) — нет. Последовательность перестановочна, если она перестановочна на любой конъюнкции, к которой применима. SUC — класс перестановочных последовательностей. Очевидно, что для перестановочных последовательностей задача применимости тривиально разрешима за полиномиальное время.

Пусть Г — последовательность импликаций, а Д — подпоследовательность Г. А называется максимальной для конъюнкции w, если все импликации Д можно применить к w одновременно, а никакая большая подпоследовательность этим свойством не обладает. Например, если Г = (о а2)(а3 а)(а5 —> а3) и w = а5, то Г имеет две максимальные подпоследовательности: (а —» о2)(а3 —а) и (а5 —о3). Ясно, что некоторая максимальная подпоследовательность может быть найдена за полиномиальное время.

Последовательность импликаций Г параллельна на конъюнкции w, к которой применима, если Г — максимальная для ш подпоследовательность самой себя, или существует максимальная для w подпоследовательность Д такая, что w Д h w' и Г \ Д параллельна на w'. Последовательность параллельна, если она параллельна на любой конъюнкции к которой применима. СС — класс параллельных последовательностей. В работе Архангельского и др. доказано, что распознавание параллельности последовательности является NP-трудной задачей.

В параграфе 2.2 мы вводим понятие сильной параллельности. Последовательность импликаций Г сильно параллельна на конъюнкции w, к которой применима, если Г — максимальная для w подпоследовательность самой себя, или для всякой максимальной для w подпоследовательности Д такой, что wA h w', Г \ Д сильно параллельна на w'. Последовательность сильно параллельна, если она сильно параллельна на любой конъюнкции к которой применима. STC — класс сильно параллельных

последовательностей. Легко видеть (теорема 2.1), что распознавание применимости сильно параллельной последовательности производится за полиномиальное время.

Следующие примеры показывают, что три класса последовательностей различны:

(а а2) (а2 -»■ а3)(а5 а) € STC \ SUC, (а2 а2)(а2 —> а) G СС \ STC.

Включение SUC С STC С СС очевидно.

Мы доказываем теоремы о сложности распознавания применимости последовательностей (2.1), о сложности распознавания перестановочности и сильной параллельности (2.2) и о сложности распознавания параллельности (теоремы 2.4 и 2.5). Результаты см. в таблице ниже.

В параграфе 2.3 мы вводим классы ¿-максимально параллельных и максимально параллельных последовательностей импликаций. Последовательность Г к-максимально параллельна на конъюнкции w (где к = 1,2,...), к которой применима, если или Г — максимальная для w подпоследовательность самой себя, или для всякой максимальной для w подпоследовательности Д длины не меньше к такой, что u;A h w', Г \ Д ¿-максимально параллельна на w', или для всякой максимальной для w подпоследовательности Д наибольшей длины такой, что гоД I- w', Г\ Д к-максимально параллельна на w'. Последовательность к-максимально параллельна, если она fc-максимально параллельна на любой конъюнкции к которой применима. MQ- — класс ¿-максимально параллельных последовательностей. Последовательность Г максимально параллельна на конъюнкции w, к которой применима, если или Г — максимальная для w подпоследовательность самой себя, или для всякой максимальной для w подпоследовательности Д наибольшей длины такой, что wA Ь w1, Г \ Д максимально параллельна на и/. Последовательность максимально параллельна, если она максимально параллельна на любой конъюнкции к которой применима. МС — класс максимально параллельных последовательностей.

В лемме 2.6 устанавливается, что МС = |J{MCfc+i : k G w}. Теорема 2.12 показывает, что классы МС^- образуют иерархию по к: M С к С MCfc+i. Из определений видно, что STC = MCi и МС С СС. Следую-

щий пример показывает, что МС ф СС:

(а2 -I а2)(а2 а) € СС \ МС. Таким образом, имеют место следующие соотношения: SUC С STC = МС! С МС2 С ...

... С MCfc С MCfc+i С ... С МС С СС.

В лемме 2.7 предлагается алгоритм выделения максимальной подпоследовательности наибольшей длины, который работает полиномиальное время, если размер алфавита зафиксирован заранее. В теореме 2.9 мы устанавливаем сложность задачи применимости последовательностей из МС^ и МС. Теорема 2.10 устанавливает сложность распознавания к-максимальной параллельности, а 2.11 — максимальной параллельности.

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

Класс Распознавание Применимость

Огр.алф. Общ.сл. Огр.алф. Общ.сл.

SUC coNP-полная р (*)

STC coNP-полная Р

MCfc coNP-полная Р

МС coNP-полная nf-полная Р NP-полная

СС лежит в П^-полная NP-полная

Как мы видим, сложность обеих задач для классов SUC, STC и МС/; совпадает: применимость разрешима за полиномиальное время, а распознавание принадлежности к классу — coNP-полная задача. Для класса СС задача применимости имеет такую же сложность как и в общем случае — NP-полная, а сложность распознавания зависит от размера алфавита. Если алфавит фиксирован, то задача принадлежит Af, иначе она является П^-полной. Класс МС ведет себя промежуточным образом: если размер алфавита фиксирован, то сложность задач эквивалентна их сложности для классов SUC, STC и МС*, а если размер алфавита неограничен, то сложность такая же как для СС.

Глава 3: сложность обновлений моделей логических программ

Пусть имеется предикатная сигнатура Е и множество констант С. Логическая програльма (ЛП) — это множество предложений вида I ■(— /х,..., /„, п > О, где I,— литералы, то есть атомные формулы или их отрицания. I в данном случае — голова предложения, 11,...,1п — его тело. Базисной назовем формулу без переменных. Интерпретация — это множество базисных атомных формул. Предложение I <— ... ,1п истинно в интерпретации 7, если для любых значений переменных в 7 либо истинно I (то есть I £ 7), либо ложно одно из (то есть и I). ЛП Ф истинна в интерпретации I (7 — модель Ф), если в 7 истинно каждое ее предложение. ЛП называется хорновской, если она не содержит отрицательных литералов, нормальной, если головы всех ее предложений положительны. Обновление — пара Д = (Г>+,7)-), где £>+ и — множества базисных атомов, и 75+ П-О- = 0. Содержательно, 7?+ — это факты, которые требуется добавить в модель, а £)_ — удалить из нее. Обновление , положительно, если = 0. Обновление Д = (7?+,7?~) выполнено в интерпретации I, если Б+ С 7 и П / = 0. Если Ф — ЛП, Д — обновление, то Асс(Ф,Д) — множество моделей Ф, в которых выполнено Д.

Пусть дана интерпретация 7. Введем на множестве интерпретаций отношение частичного порядка <7, которое характеризует количество изменений в интерпретации относительно 7:

</={(71,72):7гП7э72П7}и и{(71,72) :7!П7 = 72П7 и 7Х\/С72\7}.

Будем называть интерпретацию минимально отклоняющейся от I по отношению к Асс(Ф,Д), если 1\ — минимальный относительно порядка <1 элемент Асс(Ф, Д). Пусть О — логическая формула сигнатуры Е. Определим семантику ММ(1,А,в): МА4(1,А,0)(Ф) — это множество минимально отклоняющихся от 7 по отношению к Асс(Ф,Д) интерпретаций, в которых истинна 0. Например, если Ф = {о 6,-с}, 1 — 0, Д = ({6},0) и 0 = ->а, то Асс(Ф, Д) = {{а, &},{!>,с), {а, 6,с}}. Из них {а, 6} и {6, с} являются минимально отклоняющимися от 7, и только в {Ь,с] выполнено 0. Следовательно, _МЛ4(7, Д, 0)(Ф) = {{Ь,с}}.

Для всякой семантики 5 можно рассматривать две задачи: Б-совмест-ностъ и ¿-следование, то есть имеет ли ЛП Ф модель в £ (¿>(Ф) ф 0), и во всякой ли ¿»-модели ЛП Ф выполнена логическая формула Ф (Ф Ь^ Ф). Мы будем исследовать сложность этих задач для семантик ММ(1, Д, 0), в случае, когда формула 0 является базисной. Легко доказать (лемма 3.1), что задачи ММ(1, Д, 0)-совместности и ММ(1, Д, 0)-следования сводятся к отрицанию друг друга за полиномиальное время.

Если рассматривать модели I ЛП Ф как состояния базы данных (БД), а саму Ф — как ограничение целостности, то проблема ММ(1, Д, 0)-совместности ЛП Ф является формализацией следующей задачи: возможно ли выполнить обновление Д БД I таким образом, чтобы внести в нее как можно меньше изменений (дополнительные изменения могут потребоваться для удовлетворения ограничений целостности), и чтобы во вновь полученном состоянии было выполнено условие 0. Ф Н^,м(/,д,в) Ф означает, что любое «минимальное» обновление при выполнении 0 приводит к выполнению Ф. В частности, если 0 = 1, то Ф Кч,м(/,д,в) Ф формализует, что любое «минимальное» обновление приводит к выполнению Ф.

В параграфе 3.3 мы исследуем сложность задач ММ(1, Д, ©^совместности и ММ(1, Д, ©)-следования в случае, когда сигнатура зафиксирована. В пункте 3.3.1 приводится конструкция, позволяющая доказывать нижние оценки сложности этих задач, когда ЛП содержит переменные и сигнатура содержит хотя бы один двухместный предикатный символ (лемма 3.4). В 3.3.2 мы оцениваем сложность построения инфляционного замыкания множества литералов (лемма 3.5), и предлагаем алгоритм построения минимально отклоняющейся модели для хорновских ЛП, с помощью которого мы получаем верхние оценки сложности задач (лемма 3.6). В качестве следствия 3.6.1 получаем тест на «минимальное отклонение» одной интерпретации от другой. Пункты 3.3.3 и 3.3.4 посвящены исследованию сложности задач для хорновских ЛП. Как показано, сложность меняется в зависимости от того, допускаются ли удаления в обновлениях или разрешены только вставки. Пункт 3.3.3 посвящен исследованию задач, когда обновления положительны. В лемме 3.9 устанавливается сложности задачи ММ(1, Д, 0)-совместности в частном случае, когда формула 0 является атомной. В 3.3.4 мы рассматриваем задачу, когда обновления могут быть произвольными. В 3.3.5 исследуется сложность в самом об-

щем случае. Как показано, если ЛП не является хорновской (в т.ч. если ЛП является нормальной), то сложность не зависит от вида обновления. Полученные в параграфе 3.3 результаты о сложности представим в виде следующей таблицы (звездочкой отмечены результаты полученные ранее в работах Дехтяря, Диковского и Спиратоса3):

Совместность Следование

Без перем. С перем. Без перем. С перем.

Ф хорн., А полож. Р Rtt(NP) Р Rti(NP)

Ф — хорн. NP coNP nf

Общий случай (*) п2р (*) nf

Rtt(NP) — это класс множеств, которые сводятся к множествам из NP посредством табличной сводимости. Сложность, указанная в столбце «без переменных» относится так же к случаю, когда переменные в ЛП встречаются, но сигнатура содержит только одноместные предикатные символы. Наличие переменных существенно влияет на сложность задач, только если сигнатура содержит хотя бы один двухместный (или большей размерности) предикатный символ. Как видно из этой таблицы, за полиномиальное время обе задачи разрешимы, если ЛП является хорновской и пропозициональной, а из обновлений разрешены только вставки (теорема 3.8). Наличие хотя бы одного двухместного предикатного символа во всех случаях повышает сложность задач на один уровень полиномиальной иерархии (теоремы 3.10, 3.12 и 3.13 соответственно). Если для хорновских ЛП разрешить не только вставки, но и удаления, то сложность возрастает еще на один уровень (теоремы 3.11 и 3.12). Если рассматривать ЛП, в которых допускаются отрицания, например нормальные ЛП, то задачи относятся ко второму уровню полиномиальной иерархии для пропозициональных ЛП и к третьему для ЛП общего вида (теорема 3.13).

В параграфе 3.4 мы рассматриваем задачи ММ(1, Д, 0)-совместности и ММ(1, Д, 0)-следования, когда сигнатура не фиксирована заранее (те-

3Dekhtyar M., Dikovsky A., Spyratos N. On Conservative Enforced Updates: Proceedings of 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany, LNCS 1265 - 1997 - pp. 244-257.

Dekhtyar M., Dikovsky A., Spyratos N. On Logically Justified Updates: Proc. of the 1998 Joint International Conference and Symposium on Logic Programming. MIT Press — 1998 — pp. 250-264.

орема 3.14). Естественно, что в данном случае имеет смысл рассматривать только ЛП, содержащие переменные. Приведем результаты о сложности, установленные в 3.4:

Совместность Следование

Ф — хорновская EXP EXP

Общий случай £fxp п?хр

Как видим, если сигнатура не фиксирована, то сложность задач по-прежнему зависит от наличия отрицаний в ЛП. Если ЛП является хорновской, то обе задачи могут быть решены за экспоненциальное время. Если в предложениях ЛП допускаются отрицания (в том числе для нормальных ЛП) сложность повышается до Sfхр и П^хр для задач совместности и следования соответственно.

Глава 4: сложность совершенных моделей пропозициональных логических программ

Семантика совершенных моделей, веденная Пжимусинским4, прежде всего, интересна тем, что нормальная ЛП может иметь не более одной совершенной модели. Это позволяет выбрать из всего множества моделей одну, причем достаточно естественным способом.

Пусть дана ЛП Ф. Определим отношения < и < на множестве атомов. Пусть из предложений Ф можно построить последовательность следующего вида: о ai(-)a\Pi, aj Q2(-|)a2/32, ..., a„ an+i(-t)6/?n+i, где a, oi,..., an, b — это атомы, aj, Pi — последовательности литералов, а знаки отрицания, показанные в скобках, могут отсутствовать. В этом случае а < b по определению. Если в этой последовательности хотя бы перед одним из атомов ai,... ,ап, b стоит показанный в скобках знак отрицания, то, кроме того, а < Ъ. Таким образом, < можно рассматривать как отношение зависимости, а < — немонотонной зависимости. С интуитивной точки зрения, если а < Ъ и возникает дилемма, что включить в модель: а или Ъ, то в предпочтительнее включать а, поскольку о «выводится», а b — «предполагается». На этом основано отношение предпочтения интерпретаций: Ii <СЬ -£=> Va £ Ii \ h 3b Е h \ h а, < b. Совершенная модель

4Przymusinski Т. Perfect model semantics: Proc. Intern. Conf. on Logic Programming — 1988 - pp.1081-1096.

ЛП Ф — модель, для которой отсутствуют более предпочтительные модели. Пусть, например, ЛП Ф = {а 4— Данная логическая программа имеет три модели: l\ = {a}, I2 = {6} и I3 = {а,Ь}. По определению отношения < имеем о < b и b ¿Ç а. Поэтому I2jt.I1 и /з^Д. Как видим, Ii является совершенной моделью ЛП Ф. Заметим, что отношение <С не является антисимметричным, поэтому совершенных моделей может и не быть, как, например, у ЛП {а -6, 6 ->а}. Семантика совершенных моделей обозначается VETIT.

В параграфе 4.3 мы получаем результат, описывающий структуру совершенной модели. Введем отношение эквивалентности на атомах: а = b Ф=> а ^ b и b < а. Совершенная модель может быть описана следующим образом (алгоритм PERFCONS, леммы 4.2 и 4.3). Выберем максимальный относительно класс эквивалентности атомов Е\. Выберем <I>i — множество предложений Ф, содержащих только атомы из Е\. Проверим, имеет ли Фх единственную минимальную модель 1\. Если нет — совершенная модель отсутствует. Иначе выберем максимальный класс эквивалентности атомов Е2 из оставшихся. Выберем Фг — множество предложений Ф, содержащих только атомы из Е\ U Ео. Построим Фо из Фг заменой всех атомов из Е\ их значениями в Ii. Проверим, имеет ли Ф'2 единственную минимальную модель I2. Если нет — совершенная модель отсутствует. Иначе выберем максимальный kjiblcc эквивалентности атомов из

оставшихся, и т.д. Если совершенная модель I существует, то I = (J /j.

Как видим, процедура похожа на построение модели стратифицированной ЛП и является ее обобщением. Поскольку задача определения того, имеет ли пропозициональная ЛП единственную минимальную модель, может быть решена за полиномиальное время с NP-полным оракулом, то отсюда тривиально следует существование алгоритма, решающего задачи ■pifô-F-coBMecTHoem и ViТ^-следования за полиномиальное время с NP-полным оракулом, то есть принадлежность этих задач классу AÇ (лемма 4.1, теорема 4.4). Это является ответом на открытый вопрос работы Айтера и Готтлоба5, являются ли задачи ^-совместности и VETLT-следования для нормальных пропозициональных ЛП и nf-полными соответственно (в предположении, что полиномиальная иерархия не схло-

5Eiter Т., Gottlob G. On the computational cost of disjunctive logic programming: Propositional case // AMAI, 15 — 1995 — pp. 289-323.

пывается).

Далее, в параграфе 4.4 мы исследуем нижнюю границу сложности этих задач. Для этого мы вводим новый тип вычислительного устройства и связанный с ним класс сложности. Вычислительное устройство — разновидность машины Тьюринга с оракулом, часть вопросов которому задавать «не рекомендуется», поскольку ответом на такие вопросы является немедленное отвержение входа. Более формально: оракул представлен парой множеств (А, В) таких, что А (Л В = 0, при переходе машины Тьюринга в вопросительное состояние ответ будет положительным, если вопрос i Е А, отрицательным, если х € В, а если х ^ A U В, то в следующий момент времени машина переходит в заключительное отвергающее состояние. Класс сложности D2 — множества, распознаваемые такими машинами Тьюринга за полиномиальное время с оракулом (UMINSAT, SAT), то есть множество «плохих» вопросов представлено формулами, имеющими более одной минимальной модели (UMINSAT — это множество КНФ, имеющих в точности одну минимальную модель). Из определения класса D2 следует, что coNP С D2 С Af. Мы приводим алгоритм PERFCONS1, который решает задачу VE1ZT-совместности за полиномиальное время, используя оракул (UMINSAT, SAT). Следовательно, задача Т^Т^-еовместности лежит в D2 (лемма 4.5). Далее доказываются две технические леммы о свойствах КНФ (4.6 и 4.7), которые используются в доказательстве Юг-трудности задачи VC1ÍT-следования (лемма 4.8). Основной результат последней части — Pi7?,/"-совместность является D2-полной задачей, a V8TZT- еле до ванне — «Юг-полной (теоремы 4.9 и 4.11).

Глава 5: о структуре полных множеств для NP и ЕХР

Зафиксируем нумерацию вычислительных устройств: {9Jt¿ : i £ us}. Пусть t — некоторая функция — ограничение на время вычисления. Марковская сложность (сложность распознавания) множества А при ограничении t на время вычисления — это функция, дающая по каждому new минимальную длину |г| номера вычислительного устройства Ш¡, которое распознает начальный отрезок множества А длины п за время t(¡2:|). Колмо-горовская сложность (сложность порождения) множества А при ограничении £ на время вычисления — это функция, дающая по каждому п Е и минимальную длину |г| номера вычислительного устройства ГОТ¿, которое

порождает начальный отрезок характеристической последовательности множества А длины п за время ¿(|п|), не используя каких-либо входных данных. Аналогично определяется алгоритмическая сложность при других ограничениях на вычисления. Как известно, существуют оптимальные нумерации вычислительных устройств, относительно которых алгоритмическая сложность минимальна с точностью до констант при не более чем полиномиальном ослаблении ограничений на используемые время и память. Именно алгоритмическую сложность относительно таких нумераций мы и будем иметь в виду в дальнейшем и будем обозначать через (А'™)) и Кр (А^"') марковскую и колмогоровскую сложность соответственно начального отрезка множества А длины п при ограничении, соответствующим классу сложности V.

В параграфе 5.2 мы исследуем нижнюю границу сложности распознавания при полиномиальном ограничении на время начальных отрезков ИР-трудных по Тьюрингу множеств. Мы устанавливаем (теорема 5.1), что для любого КР-трудного по Тьюрингу множества А

МР ^(п)^ > к^П

для любого к для бесконечно многих п (если Р ф ЫР). Это означает, что если Р ф КР, то невозможно найти простой алгоритм, который распознавал бы некоторое ЫР-трудное по Тьюрингу множество на достаточно большом начальном отрезке за полиномиальное время (именно такое решение задачи является практически значимым). В качестве следствия (5.1.1) получаем, что никакое КР-трудное по Тьюрингу множество не может быть «гиперунарным», то есть подмножеством {22 — 1 : п € и;}. Это является ответом на открытый вопрос из работы Дехтяря6. Таким образом, КР-трудные по Тьюрингу множества не могут иметь очень простую структуру. Вопрос об усилении этого результата — можно ли повысить нижнюю границу марковской сложности начальных отрезков длины п NP-тpyдныx по Тьюрингу множеств до к п (если Р Ф МР) — оставлен открытым. Этот результат является естественным дополнением к результатам о структуре КР-полных и трудных множеств относительно других

6Дехтярь М.И. О сводимости к «редким* множествам и плотности NP-полных задач. // Автоматы, алгорифмы, языки. Межвузовский тематический сборник. — Калинин, 1982 — сс. 42-52.

сводимостей7.

В параграфе 5.3 мы рассматриваем верхнюю границу алгоритмической сложности порождения множеств, к которым сводятся проблемы из EXP П ESPACE. Этот результат является усилением результата работы Бука и Лютца8. Основной результат (теорема 5.2, следствие 5.2.2) может быть сформулирован следующим образом: Пусть V — некоторый класс сложности, и ЕХРП ESPACE С V. <р — произвольная сводимость, не сильнее <fg|u|_T (сводимость по Тьюрингу с не более чем логарифмическим относительно длины входа числом вопросов к оракулу). Пусть А и В — множества, A G V, А <р В и почти для всех п

Kv (ß(n>) > та — р(Igл)

для некоторого полинома р {п). Тогда существует редкое множество S и А <р S. Это утверждение усиливает результат Бука и Лютца следующем смысле:

• Мы рассматриваем произвольный класс V Э EXPftESPACE, вместо ESPACE.

• Верхняя граница алгоритмической сложности установлена равной п — p(lg п) с произвольным полиномом р, вместо п — 2 lg п.

• Мы распространяем результат на произвольную сводимость, не превосходящую jnj_j. , вместо ограниченной табличной сводимости.

В качестве следствия (5.2.1) получаем, что ЕХР-трудные множества в смысле сводимости |п|не могут иметь сложность начального отрезка длины п большую п — p(lg п) почти для всех п при экспоненциальном ограничении на время вычисления.

Благодарности

Автор выражает глубокую благодарность научному руководителю доценту М.И.Дехтярю, а также профессору М.А.Тайцлину за ценные советы.

7см., например, Complexity theory. Retrospective II. / Ed. Hemachandra L. A., Selman A. L. — New York, Springer-Verlag, 1997.

8Book R. V., Lutz J. H. On languages with very high information content: 7th Structural complexity theory — 1992 — pp. 255-259.

Список литературы

[1] Dudakov S.M. The Concurrency Complexity for the Horn Fragment of Linear Logic: Proc of the fourth Intern. Simp. LFCS'97. — Springer, 1997 — pp. 78-87.

[2] Dudakov S.M. On information content of hard sets: Материалы международной конференции по математической логике, посвященной 90-летию со дня рождения А.И.Мальцева (тезисы докладов). — Новосибирск, 1999 — сс. 79-80.

[3] Dudakov S.M. On the complexity of perfect models of logic programs. // Fundamenta Informaticae. — vol. 39(3) — 1999 — pp. 249-258.

[4] Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases: Proc. of 5th International Conference LPNMR'99 — Berlin, Springer-Verlag, 1999 — pp. 132-146.

В работе [4] автору принадлежат пункты (1) и (2) теоремы 1 из параграфа 3.1.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Дудаков, Сергей Михайлович

Введение

1 Основные понятия и определения

1.1 Классы сложности и типы сводимости.

1.2 Логические программы.

2 Сложность параллельности для хорновского фрагмента линейной логики

2.1 Основные понятия лин&йной логики.

2.2 Перестановочность, параллельность и сильная параллельность

2.3 Максимальная параллельность.

3 Сложность обновлений моделей логических программ

3.1 Постановка задачи.

3.2 Определения.

3.3 Сложность задач при фиксированной сигнатуре.

3.3.1 Вспомогательная конструкция: J и Т

3.3.2 Алгоритм построения обновления для хорновских ЛП

3.3.3 Ф — хорновская, А положительно.

3.3.4 Ф — хорновская, А произвольно.

3.3.5 Общий случай.

3.4 Случай нефиксированной сигнатуры.

4 Сложность совершенных моделей пропозициональных логических программ

4.1 Совершенные модели логических программ.

4.2 Определения.

4.3 Структура совершенных моделей.

4.4 Нижняя оценка сложности совершенных моделей

5 О структуре полных множеств для NP и EXP

5.1 Основные понятия и определения

5.1.1 Структурная теория сложности.

5.1.2 Информационная сложность проблем.

5.2 Алгоритмическая сложность и плотность

NP-трудных множеств

5.3 О множествах, сводимых к множествам с большой колмого-ровской сложностью.

Введение диссертация по математике, на тему "Вычислительная сложность некоторых задач математической логики"

Актуальность

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

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

Линейная логика является расширением классической и содержит внутри себя средства описания ресурсов, «запас» которых ограничен. Как и в классической логике, важной частью линейной логики является ее хор-новский фрагмент с использованием мультипликативных связок, прежде всего, потому что он имеет прозрачную ресурсную семантику: хорновские импликации линейной логики можно рассматривать как некоторые преобразования (операции обмена) ресурсов, а доказуемость секвенции с их использованием — как возможность полностью осуществить все эти преобразования. Поскольку выводимость в хорновском фрагменте линейной логики является NP-полной задачей, то встает вопрос отыскания интересных (достаточно естественных) частных случаев, когда она может быть решена за полиномиальное время. Одним из наиболее естественных способов является «распараллеливание» вывода за счет использования как можно большего количества импликаций за один шаг. Оценкам эффективности такого распараллеливания посвящена глава 2 данной диссертации.

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

Еще одна важная задача, связанная с логическими программами, — это построение модели с заранее определенными свойствами. Как известно, логическая программа может иметь несколько моделей, поэтому часто возникает задача сужения множества моделей, а в идеале — выбора одной из них, опираясь на какие-либо естественные свойства. Одним из способов решения этой проблемы может быть использование совершенных моделей, которые предложены Пжимусинским [55]. Недостатком этого приема является то, что не всякая логическая программа имеет совершенную модель. Поэтому возникает задача: определить по заданной логической программе существует ли у нее совершенная модель. Частично данная задача решена в работе [28], а в данной работе в главе 4 мы даем точную оценку сложности и отвечаем на отрытый вопрос из [28].

Обзор литературы

Те области теории алгоритмов, которым посвящена данная работа, интенсивно развиваются. Ежегодно проводятся десятки конференций и издаются десятки журналов, посвященных применению методов математической логики при решении различных задач информатики, в частности, логического программирования, баз данных и др. В этом кратком обзоре мы, конечно, не можем охватить все источники, темы которых так или иначе связаны с темой диссертации. Здесь мы отметим только те монографии, на определения и результаты из которых мы прямо ссылаемся в работе, и статьи, темы которых непосредственно связаны с темами нашего исследования и его результатами. Более полные библиографии можно найти, например, в [15, 7, б, 19, 46]. Кроме того, большое число библиографий доступно через Интернет, например, по адресам: http://www.Stanford.edu/~iliano/linearbib/llb.html (библиография по линейной логике) и http://www.ессс.uni-trier.de/eccc по структурной теории сложности).

Общей теории вычислимости и алгоритмическим сводимостям посвящена книга [4].

В [33, 52] рассматривается вычислительная сложность различных задач, приводятся определения классов вычислительной сложности, примеры задач полных и трудных для различных классов, дается обзор наиболее существенных сведений о структуре полных множеств.

Линейная логика впервые была предложена Жираром в работе [35]. Там же была высказана идея о связи доказательств в линейной логике с параллельными вычислениями. В [47] доказано, что уже пропозициональная часть линейной логики является алгоритмически неразрешимой и поставлена задача о сложности доказательств в хорновском фрагменте. Канович в [41] показал, что задача выводимости в хорновском фрагменте является NP-полной. Другое доказательство того же факта приведено в [10], из него также следует, что задача остается NP-полной даже над алфавитом из двух символов. В [11] даны определения двух классов последовательностей хорновских импликаций — классы перестановочных и параллельных последовательностей. Для перестановочных последовательностей задача выводимости разрешима за полиномиальное время. Там же предложено полиномиально проверяемое условие перестановочности и доказано, что задача распознавания параллельности является NP-трудной.

Основные концепции логического программирования изложены в [48]. Задача обновления моделей логических программ рассматривалась с конца 80-х годов, но наиболее активно стала изучаться в последние несколько лет в связи с появлением концепции активных баз данных (то есть баз данных, использующих средства искусственного интеллекта при осуществлении обновлений) [20,13, 54]. Изначально интерес такого рода вызывался необходимостью средств усиления выразительности SQL-подобных языков обновления [7]. В [23, 24, 37] предложено использовать логические программы в качестве ограничения целостности баз данных, которые используются для автоматического разрешения конфликтов, возникающих при обновлениях. При обновлениях обычно рассматривается два типа задач [28]. «Оптимистические» — когда достаточно, чтобы существовал способ выполнить обновление с соблюдением некоторых условий, — и «пессимистические» — когда необходимо, чтобы любой способ выполнения обновления приводил бы к выполнению условия.

Имеется большое количество результатов о различных семантиках логических программ, которые допускают отрицания в условиях предложений (нормальные логические программы) (см., например, [8]). Семантика совершенных моделей была предложена в [55] и основана на форме записи предложений. Известно [55, 56], что нормальная логическая программа может иметь не более одной совершенной модели. В [9] показано, что для стратифицированных логических программ совершенная модель всегда существует и является единственной стабильной моделью (о стабильных моделях см. [50] и более подробно [51]). В [29] установлено, что для дизъюнктивных логических программ определение существования совершенной модели является Е^-полной, а выводимости — nf-полной проблемой. В этой же работе установлены приблизительные границы сложности этих проблем для недизъюнктивных программ, а точная оценка их сложности сформулирована в качестве одной из открытых проблем.

Теория алгоритмической сложности была создана в работах Колмогорова, Соломонова, Чейтина и их учеников. Основы этой теории и ее современное состояние изложены в [1] и [46]. Работа [21] посвящена исследованию алгоритмической сложности рекурсивных множеств при ограничении на время вычисления. [15, 39] представляют собой обзоры результатов по структурной теории сложности. Наиболее значимые современные результаты из этой области собраны также в [40]. В работе [38] доказано, что если Р ф NP, то не существует редких Ш-трудных в NP множеств. В [2] показано, что при Р ф NP также не существует трудных по Тьюрингу для NP множеств, имеющих очень низкую алгоритмическую сложность: меньше к lg lg lg п для начального отрезка множества длины п. В качестве открытого в этой работе поставлен вопрос о том, можно ли усилить данный результат, повысив алгоритмическую сложность, при которой множества не могут быть NP-трудными. Основная теорема работы [14] говорит о том, что множества, к которым Ш-сводятся не сводящиеся к редким множества из ESPACE можно «слегка сжать», то есть сложность А^ в бесконечном числе точек меньше чем п — 2 lg п.

Цели работы

2. Исследовать сложность задач обновления моделей логических программ в зависимости от сигнатуры, вида программы и вида обновления.

3. Установить сложность задачи построения совершенных моделей нормальных пропозициональных логических программ и задачи выводимости в совершенных моделях.

4. Выяснить возможность усиления результатов из [2, 14], связанных с алгоритмической сложностью и плотностью NP и ЕХР-трудных множеств.

Апробация работы

Первая часть работы докладывалась на международной конференции по математическим основаниям информатики LFCS'97 [27], вторая — на международной конференции по логическому программированию и немонотонному выводу LPNMR'99 [22]. Содержание главы 4 о совершенных моделях логических программ было опубликовано в журнале «Fundamenta Informa-ticae» [26]. Содержание последней части настоящего исследования было опубликовано в виде тезисов на конференции «Мальцевские чтения», посвященной 90-летию со дня рождения А.И.Мальцева [25].

Результаты, изложенные в настоящей диссертации неоднократно докладывались на семинаре по компьютерной логике ТвГУ. Содержание диссертации было представлено на семинаре МГУ по математической логике.

Структура диссертации

Диссертация состоит из настоящего введения, пяти глав основной части, заключения и списка литературы.

В главе 1 приводятся основные определения, которые используются в диссертации. Параграф 1.1 посвящен определениям, касающимся сложности вычислений, сводимостям, трудным и полным задачам, а в параграфе 1.2 мы напоминаем основные понятия, относящиеся к логическим программам.

Глава 2 посвящена исследованию сложности задачи выводимости в хор-новском фрагменте линейной логики для различных классов последовательностей хорновских импликаций и сложности распознавания принадлежности последовательностей хорновских импликаций к этим классам. В параграфе 2.2 мы исследуем классы перестановочных и параллельных последовательностей хорновских импликаций, введенных в [11], а также сильно параллельных последовательностей. Мы устанавливаем, что сложность распознавания параллельности зависит от того, ограничен ли размер алфавита заранее или нет. В параграфе 2.3 мы вводим понятие к-максимальной параллельности для каждого к = 1,2,. и максимальной параллельности, а также классы fc-максимально параллельных и максимально параллельных последовательностей хорновских импликаций. Мы устанавливаем, что классы ^-максимально параллельных последовательностей образуют иерархию по к, которая лежит между классами сильно параллельных и параллельных последовательностей. Сложности задач для класса ^-максимально параллельных последовательностей оказываются такими же, как и для классов перестановочных и сильно параллельных последовательностей хорновских импликаций. Сложность задач для класса максимально параллельных последовательностей хорновских импликаций зависит от ограниченности размера алфавита: при фиксированном размере алфавита сложность задач эквивалентна сложности задач для классов перестановочных, сильно параллельных и ^-максимально параллельных последовательностей, а если размер алфавита может быть произвольным, то сложность оказывается такой же, как и для класса параллельных последовательностей при нефиксированном алфавите.

В главе 3 мы рассматриваем сложность задачи обновления моделей логических программ. В параграфе 3.2 мы даем основные определения, связанные с данной задачей, формулируем понятие «минимального обновления». В 3.3 мы рассматриваем сложность задачи обновления, когда сигнатура зафиксирована. Данный параграф разбит на пять частей. Подпара-графы 3.3.1 и 3.3.2 носят вспомогательный характер: в первом из них мы приводим конструкцию, позволяющую доказывать нижнюю оценку сложности в случае, когда логическая программа содержит переменные, во втором — предлагаем способ построения минимально отклоняющейся модели, когда логическая программа является хорновской. Остальные три подпа-раграфа посвящены непосредственно исследованию сложности задачи обновления: в 3.3.3 рассматривается случай хорновских логических программ и положительных обновлений (вставок), в 3.3.4 — хорновских программ и произвольных обновлений, а в подпараграфе 3.3.5 — случай логических программ с отрицаниями (как следует из доказательства, вид обновления в этом случае не играет роли). Параграф 3.4 посвящен исследованию сложности задачи обновления моделей логических программ при нефиксированной сигнатуре. Мы показываем, что сложность этой задачи также зависит от того, является логическая программа хорновской или нет.

В главе 4 мы занимаемся исследованием сложности совершенных моделей нормальных пропозициональных логических программ. В параграфе 4.2 даны основные определения, а также некоторые технические понятия, используемые в доказательствах. Параграф 4.3 посвящен исследованию структуры совершенных моделей логических программ, основной результат которого — это алгоритм построения совершенной модели логической программы за полиномиальное время с NP-полным оракулом, то есть доказательство принадлежности задачи классу сложности Af. В параграфе 4.4 мы изучаем нижние оценки сложности задач совместности и выводимости в семантике совершенных моделей. Для этого мы вводим новый класс вычислительных устройств — разновидность машин Тьюринга с оракулом — и связанный с ним класс сложности — D2. Мы доказываем, что сложности задач совместности и следования в семантике совершенных моделей являются Вг-полными и соОг-полными соответственно.

5 глава посвящена исследованию алгоритмической сложности начальных отрезков NP-трудных и ЕХР-трудных проблем. Определения, связанные с алгоритмической сложностью, приводятся в 5.1.2. Параграф 5.2 посвящен исследованию нижней границы алгоритмической сложности NP-трудных по Тьюрингу множеств. Мы устанавливаем, что такие множества не могут иметь сложность к lg lg п (или меньше) начальных отрезков длины п почти для всех п. Параграф 5.3 посвящен исследованию множеств с высокой алгоритмической сложностью, «случайных» множеств. Мы устанавливаем, что хотя эти множества содержат максимально возможное количество информации, с практической точки зрения она мало полезна — любое множество из ЕХР П ESPACE, которое можно свести к «случайному», можно свести и к редкому.

В заключении приводятся основные результаты исследования.

Заключение диссертации по теме "Математическая логика, алгебра и теория чисел"

Заключение

В работе решены следующие задачи:

1. (а) Определена сложность задач распознавания и применимости для классов перестановочных, параллельных и сильно параллельных последовательностей хорновских импликаций.

Ь) Предложены понятия ^-максимальной параллельности и максимальной параллельности. Для классов ^-максимально параллельных и максимально параллельных последовательностей хорновских импликаций установлена сложность задач распознавания и применимости.

Оценки сложности задач, которые получены в настоящей работе и статье [11] (см. сноски), приведены в таблице 6.1.

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

1. Агафонов В.Н. Сложность алгоритмов и вычислений. Часть 2. — Новосибирск, изд-во НГУ, 1975.

2. Дехтярь М.И. О сводимости к «редким» множествам и плотности NP-полных задач. // Автоматы, алгорифмы, языки. Межвузовский тематический сборник. — Калинин, 1982 — сс. 42-52.

3. Мучник А.А. Добавление переводчика к статьям «Об альтернировании, I, II». // Кибернетический сборник, вып. 20. — Москва, Мир, 1983, сс. 141-158.

4. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. — Москва, Мир, 1972.

5. Трахтенброт Б.А. Сложность алгоритмов и вычислений. — Новосибирск, изд-во НГУ, 1967.

6. Чери С., Готлоб Г., Танка Г. Логическое программирование и базы данных. — Москва, Мир, 1992.

7. Abiteboul S. Updates a new Frontier: Proc. of the Second International Conference on the Theory of Databases, ICDT'88. LNCS 326 - 1988 -pp. 1-18.

8. Apt K. Logic programming, chapter 10 in van Leeuwen ed. Handbook of Theoretical Computer Science, Elsevier Science — 1990.

9. Apt K., Blair H., Walker A. Towards a theory of declarative knowledge. // Foundations of Deductive Databases and Logic Programming — 1988 — pp. 99-148.

10. Archangelsky D.A., Taitslin M.A. Linear Logic With Fixed Resources. // Annals of Pure and Applied Logic, v. 67 — 1994 — pp. 3-28.

11. Arvind V., Han Y., Hemachandra L., Kobler J., Lozano A., Mundhenk M., Ogiwara M., Schoning U., Silvestri R., Thierauf T. Reduction to sets of low information content, j j Complexity theory. — Cambridge, Cambridge University Press, 1993 — pp. 1-46.

12. Baral C., Lobo J. Formal Characterization of Active Databases: Logic in Databases. Intern. Workshop LID'96. Proceedings. — San Milano, Italy. — 1996 pp. 175-195.

13. Book R. V., Lutz J. H. On languages with very high information content: 7th Structural complexity theory — 1992 — pp. 255-259.

14. Buhrman H., Torenvliet L. On the structure of complete sets: 9th Structural complexity theory — 1994 — pp. 118-133.

15. Chandra A.K., Kozen D.C., Stockmeyer L.J. Alternation. // J. Ass. Comput. Mach., v.28, № 1 1981 - pp. 114-133.

16. Complexity Theory. Retrospective II. / Editors: Hemaspaandra L.A., Selman A.L. — New-York, Springer-Verlag, 1997.

17. Cook S.A. The complexity of theorem proving procedures: Proceeding of the 3rd Annual ACM Symposium on theory of computing — 1971 — pp. 151-158.

18. Dantsin E., Eiter Т., Gottlob G., Voronkov A. Complexity and Expressive Power of Logic Programming: Proc. 12th Annual IEEE Conference on Computational Complexity (CCC'97) Ulm, 1997 - pp. 1-20.

19. Dayal U., Hanson E., and Widom J. Active database systems. I j Modern Database Systems. — Addison Wesley, 1995 — pp. 436-456

20. Dekhtyar' M.I. Complexity spectra of recursive sets and approximability of initial segments of complete problems. // Elektronische Informations-verarbeitung Kybernetik, 15 — 1979 — pp. 11-32.

21. Dekhtyar M., Dikovsky A., Dudakov S., Spyratos N. Monotone Expansion of Updates in Logical Databases: Proc. of 5th International Conference LPNMR'99 Berlin, Springer-Verlag, 1999 - pp. 132-146.

22. Dekhtyar M., Dikovsky A., Spyratos N. On Conservative Enforced Updates: Proceedings of 4th International Conference, LPNMR'97. Dagstuhl Castle, Germany, LNCS 1265 1997 - pp. 244-257.

23. Dekhtyar M., Dikovsky A., Spyratos N. On Logically Justified Updates: Proc. of the 1998 Joint International Conference and Symposium on Logic Programming. MIT Press 1998 - pp. 250-264.

24. Dudakov S.M. On information content of hard sets: Материалы международной конференции по математической логике, посвященной 90-летию со дня рождения А.И.Мальцева (тезисы докладов). — Новосибирск, 1999 сс. 79-80.

25. Dudakov S.M. On the complexity of perfect models of logic programs. // Fundamenta Informaticae. vol. 39(3) - 1999 — pp. 249-258.

26. Dudakov S.M. The Concurrency Complexity for the Horn Fragment of Linear Logic: Proc of the fourth Intern. Simp. LFCS'97. — Springer, 1997 pp. 78-87.

27. Eiter, Т., Gottlob, G. On the complexity of propositional knowledge base revision, updates, and counterfactuals. // Artificial Intelligence 57 — 1992 pp. 227-270.

28. Eiter Т., Gottlob G. On the computational cost of disjunctive logic programming: Propositional case // AMAI, 15 — 1995 — pp. 289-323.

29. Eiter Т., Gottlob G. Propositional circumscription and extended closed world reasoning are Ilf -complete: Theoretical Computer Science, 114(2) — 1993 pp 231-245.

30. Fischer M., Rabin M. Super exponential complexity of Presburger's arithmetic: SIAM AMS Proc., 7 1974 - pp.27-41.

31. Fu B. With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets: Proc. Structure in Complexity Theory 8th annual conference — San Diego, IEEE computer society press, 1993 — pp.185-193.

32. Garey M.R., Johnson D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness. — San Francisco, W.H.Freeman and Company, 1979.

33. Gelfond M., Lifschitz V. The stable model semantics for logic programming: Proc. 5th International Conf. and Symp. on Logic Programming. — The MIT Press, 1988 pp. 1070-1080.

34. Girard J.Y. Linear Logic: Theoretical Computer Science, v. 50 — 1987 — pp. 1-102.

35. Grant J., Minker J. Integrity constraints in knowledge based systems, j j Knowledge engineering, vol 1 and 2. — Mcgraw-Hill Publishers, 1990 — pp. 1-25.

36. Halfeld Ferrari Alves M., Laurent D., Spyratos N., Stamate D. Update rules and revision programs. / Rapport de Recherche Universit£ de Paris-Sud, Centre d'Orsay, LRI 1010 № 12 1995.

37. Homer S., Longpre L. On reductions of NP sets to sparse sets: 6th Structural complexity theory — 1991 — pp. 79-88.

38. Hemachandra L. A., Ogiwara M. How hard are sparse sets: 7th Structural complexity theory 1992 - pp. 222-238.

39. Complexity theory. Retrospective II. / Ed. Hemachandra L. A., Selman A. L. — New York, Springer-Verlag, 1997.

40. Kanovich M.I. Horn Programming in Linear Logic is NP-complete: Proc.7-th Annual IEEE Symposium on Logic in Computer Science — 1992 pp. 200-210.

41. Kadin J. pNplosn] and sparse Turing complete sets of NP. // Journal of Computer and System Sciences, 39(3) 1989 - pp. 282-298.

42. Karp R.M. Reducibility among combinatorial problems. // Complexity of Computer Computations. — New-York, Plenum Press — 1972 — pp. 82104.

43. Karp R., Lipton R. Some connections between nonuniform and uniform complexity classes: Proc. of the 12th ACM Symp. of Theory of Computing 1980 - pp.302-309.

44. Ladner R., Lynch N., Selman A. Comparison of polynomial-time reduc-ibilities. // Theoretical Computer Science, № 1 — 1975 — pp. 103-123.

45. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and it's Application. — Springer — 1998.

46. Lincoln P., Mitchell J., Scerdov A., and Shankar N. Decision Problems for Propositional Linear Logic: Proc.31-th IEEE Symposium on Foundation of Computer Science — 1990 — pp. 662-671.

47. Lloyd J.W. Foundations of Logic Programming. Second, Extended Edition. — Springer-Verlag, 1993.

48. Mahaney S. Sparse complete sets for NP: Solution of a conjectute of Berman and Hartmanis. // Journal of Computer and System Sciences, 25(2) 1982 - pp.130-143.

49. Marek W., Truszczynski M. Autoepistemic logic. // Journal of ACM, 38, 3 1991 - pp. 588-619.

50. Marek W., Truszczynski M. Nonmonotonic logics; context-dependent reasoning. Springer-Verlag — 1993.139

51. Meyer A.R., Stockmeyer L.J. The equivalence problem for regular expressions with squaring requires exponential time: Proc.l3th Ann. Symp. on Switching and Automata Theory — 1972 — pp. 125-129.

52. Ogiwara M., Watanabe O. On Polynomial-time bounded truth-table reduc-ibility of NP sets to sparse sets. // SIAM Journal on Computing, 20(3) — 1991 pp.471-483.

53. Picouet Ph., Vianu V. Expressiveness and Complexity of Active Databases: 6th Int. Conf. on Database Theory, ICDT'97. LNCS 1186 1997 - pp. 155-172

54. Przymusinski T. On semantics of stratified deductive databases. // Foundations of Deductive Databases and Logic Programming — 1988 — pp. 433-443.

55. Przymusinski T. Perfect model semantics: Proc. Intern. Conf. on Logic Programming 1988 - pp. 1081-1096.

56. Stockmeyer L.J. The polynomial time hierarchy: Theoretical Computer Science, v. 3, № 1 1977 - pp. 1-22.

57. Ukkonen E. Two results on polynomial time truth-table reductions to sparse sets // SIAM J. Comput. Vol. 12, No. 3 1983 - pp. 580-587.