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

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

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

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

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

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

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

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

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

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

Те области теории алгоритмов, которым посвящена данная работа, интенсивно развиваются. Ежегодно проводятся десятки конференций и издаются десятки журналов, посвященных применению методов математической логики при решении различных задач информатики, в частности, логического программирования, баз данных и др. В этом кратком обзоре мы, конечно, не можем охватить все источники, темы которых так или иначе связаны с темой диссертации. Здесь мы отметим только те монографии, на определения и результаты из которых мы прямо ссылаемся в работе, и статьи, темы которых непосредственно связаны с темами нашего исследования и его результатами. Более полные библиографии можно найти, например, в [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 п.

Цели работы.

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

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.