СССР Л.А. Левиным [Левин, 1973], который ввел класс универсальных переборных задач. Этот класс аналогичен классу NP-полных задач и, по мнению С.А.Кука [Cook, 1971], является более сильным понятием. Однако интерпретация Л.А.Левина осталась незамеченной.
Впоследующее десятилетие усилиями многочисленных исследователей класс NP-полных задач расширился до нескольких тысяч [Гэри, 1982], а к известным классам сложности добавились новые классы [Стокмейер, 1989]. Было установлено, что значительная часть прикладных систем, в которых применяются методы искусственного интеллекта, содержит задачи, относящиеся к классу NP-полных. В связи с этим были обозначены следующие основные пути преодоления "проклятия размерности":
1) поиск приближенных методов решения NP-полных задач (эвристики, правдоподобный вывод, интервальные оценки, теория нечетких множеств и нечеткого вывода);
2) поиск подклассов NP-полных задач, для которых решение возможно с помощью алгоритмов полиномиальной сложности (представление сложных структур в виде иерархических, использование в системах логического вывода хорновских дизъюнктов и т.д.);
3) использование нейросетевых систем.
Однако основная проблема теории сложности вычислений – возможно ли решение всех задач класса NP с помощью алгоритма полиномиальной сложности – остается нерешенной. В частности, известно немало точных алгоритмов решения задачи SAT. Но, в общем случае, для решения этой задачи требуется огромное число операций, требующих таких вычислительных ресурсов (времени или памяти), которые не может обеспечить даже современная вычислительная техника. Количественная оценка требуемых для выполнения алгоритма ресурсов называется вычислительной сложностью алгоритма решения задачи.
Внастоящее время открыто несколько классов вычислительной сложности [Гэри, 1982], которая оценивается как функция от объема входных условий задачи. Для задачи "выполнимость КНФ" такой объем есть общее число литералов в заданной КНФ (пусть это будет число N). Один из простых с точки зрения реализации классов называется полиномиальным, его вычислительная сложность определяется как полином от N c фиксированными коэффициентами
55
и степенями. В этом случае при возрастании N число необходимых для выполнения алгоритма операций возрастает, но интенсивность этого возрастания считается вполне приемлемой даже в том случае, когда максимальная степень полинома равна 10. Вычислительная сложность многих задач оценивается полиномом первой (линейная вычислительная сложность) или второй степени.
Более трудным считается класс, в котором функция вычислительной сложности выражена экспонентой. В этом случае вычислительная сложность алгоритма называется экспоненциальной, и вполне возможна ситуация, когда для алгоритма такой сложности даже при N 50 время решения на современных компьютерах будет исчисляться неделями или месяцами. Задачи с экспоненциальной оценкой вычислительной сложности называются NP-полными, и "выполнимость КНФ" относится к этому классу задач. Уже найдено немало классов КНФ, для которых алгоритм решения имеет полиномиальную сложность. Например, доказано [Krom, 1967], что если в некоторой КНФ каждый дизъюнкт содержит не более двух литералов, задача выполнимости всегда может быть решена с помощью алгоритма полиномиальной сложности. Но для общего случая полиномиального алгоритма пока что не найдено. К тому же пока не известно, существует ли вообще такой алгоритм.
Задачи, выходящие по вычислительной сложности за пределы NP-полных задач, входят в класс #P-полных [Гэри, 1982], т.е. задач перечисления. В частности, если требуется не просто установить выполнимость КНФ (найти хоть одну выполняющую подстановку), а указать количество всех ее выполняющих подстановок, то задача реализуется, в общем случае, алгоритмами со сложностью выше экспоненциальной и относится к
#P-полным.
Несмотря на многочисленные привлекательные свойства аксиоматического подхода и его большую популярность (особенно среди теоретиков), он обладает, по крайней мере, одним существенным недостатком. Дело в том, что алгоритмы, используемые в этих системах, не обладают свойством детерминированности – в нетривиальных случаях перед каждым этапом построения доказательства необходимо сделать выбор среди различных путей, т.е. ответить на вопросы: "какие применить правила вывода и к каким
56
аксиомам или выведенным ранее предложениям?" или "какие пары дизъюнктов необходимо взять, чтобы применить к ним принцип резолюции?". Неправильный выбор часто ведет к тупику или к слишком длинному доказательству. Детерминированность здесь достигается за счет того, что доказательство строится по принципу дерева вывода: просматриваются подряд все ветви этого дерева до тех пор, пока не получится положительный результат (в теории алгоритмов такой метод называется поиском с возвращением или методом ветвей и границ [Рейнгольд, 1980]). Если же формула невыводима (теорема недоказуема), а мы этого заранее не знаем, то для получения результата приходится просматривать все ветви дерева вывода, что достигается только алгоритмами экспоненциальной сложности. Как следствие, возрастают сложность программного обеспечения, предназначенного для логического анализа систем, и затраты вычислительных ресурсов.
1.4. Отношения в математике и информационных системах
Ранее мы рассмотрели язык предикатов – универсальный язык представления знаний в системах искусственного интеллекта, а также привели обзор некоторых систем логического вывода и указали на их взаимосвязь с соответствующими алгебраическими системами, относящимися к классу булевых алгебр. Было установлено, что при реализации процедур логического вывода возможны две альтернативы: 1) организовывать вывод в рамках некоторого исчисления путем построения дерева вывода; 2) алгебраически устанавливать выводимость логических формул или обосновывать корректность вывода.
В рамках современной логики вторая альтернатива, как правило, серьезно не рассматривается, поскольку считается, что она порождает более трудоемкие алгоритмы. Однако теория формальных систем, пришедшая на смену алгебраическому подходу, не предложила принцип решения проблемы экспоненциальной катастрофы, и вычислительная сложность процедур вывода осталась по-прежнему высокой.
С появлением вычислительной техники вновь встал вопрос о том, какой подход лучше применять при компьютерной реализации задач логического анализа: алгебраический или основанный на теории формальных систем. Легко понять, что вычислительная техника, построенная на аппарате булевых алгебр,
57
более приспособлена для алгебраических методов. Этим объясняется, например, популярность реляционной алгебры в управлении данными.
В отличие от алгебраических операций, символьные преобразования, лежащие в основе ТФС, плохо приспособлены для их распараллеливания. Учитывая, что интерпретациями большинства систем логического вывода являются те или иные булевы алгебры, естественно предположить, что именно на основе алгебраического подхода целесообразно (по возможности) строить программное обеспечение, предназначенное для решения логических задач.
Часто в прикладных задачах, где исследуется некоторые процессы, необходимо не просто ответить на вопрос об их осуществимости или неосуществимости, но и оценить параметры, при которых они осуществимы. Средствами TФС задачи оценки параметров трудно реализуемы. Как уже упоминалось, большинство типичных для ТФС задач сводятся к выполнимости КНФ, но не к оценке ее выполняющих подстановок. В терминах же алгебраических систем не всегда удается даже описать требуемые методы логического анализа.
По мнению авторов, для развития алгебраических методов логического анализа необходимо найти математическую структуру, которая бы позволила представлять основные виды данных и знаний подобно тому, как они представляются на языке предикатов в рамках ТФС. "Алгебраический аналог" предиката – многоместное отношение. Как показано далее, многие системы знаний можно представить математически не только посредством определенного искусственного языка, но и в виде совокупности отношений, с которыми выполняются специальные операции, сопоставления и преобразования. Некоторые из этих преобразований можно непосредственно соотнести с отдельными видами логического анализа рассуждений. В истории математики проблема связи логики и теории отношений возникала неоднократно. Так, немецкий математик И. Юнг в своей работе, опубликованной в 1638 году, показал, что классическая силлогистика не в состоянии охватить некоторые методы логического анализа, используемые в научных рассуждениях. Юнг пытался построить теорию несиллогистических выводов, которую в настоящее время можно рассматривать как часть теории отношений [Стяжкин, 1967]. Английский математик и логик А. де Морган (1806–1871) в ряде своих работ рассматривал связь логики и теории отношений
58
и по праву считается родоначальником современной теории отношений. Он не только систематизировал и открыл некоторые законы логики (один из законов носит его имя), но и впервые определил операции с отношениями (композиция, обращение и др.) Однако общая теория отношений, пригодная для задач логического анализа, пока полностью не разработана. В частности, как было показано в п. 1.3, операции пересечения и объединения не определены для многоместных отношений, заданных в различных схемах, то есть недостаточно исследована связь алгебры множеств с теорией многоместных отношений.
Под теорией отношений в современной математике и информационных системах подразумевается либо теория бинарных отношений, либо теория многоместных отношений, в основе которой лежит реляционная алгебра.
В любом случае используется классическое определение отношения через декартово произведение множеств.
Заметим, что в системах искусственного интеллекта активно применяются методы моделирования естественных рассуждений на основе теории бинарных отношений. Как показано в последующих главах, создание общей теории многоместных отношений позволяет значительно расширить область применения алгебраического подхода при решении задач логического анализа, давая новые возможности логического вывода и не ограничиваясь только им.
1.4.1. Понятие "отношение" и декартово произведение множеств
Объектами алгебры множеств могут быть не только видимые или воображаемые предметы, но и разнообразные математические структуры: числа, точки, линии, интервалы, аналитические функции и т.д. Часто встречаются последовательности из двух, трех и т.д. элементов. Такие последовательности в математике называют n-местными последовательностями, n-ками, кортежами. Будем использовать термин элементарный кортеж. Количество элементов элементарного кортежа называется размерностью этого кортежа. Понятно, что элементарные кортежи одной размерности могут отличаться типами элементов.
Множество однотипных элементарных кортежей одной и той же размерности n называют многоместным (или n-местным) отношением. Широко используемая разновидность многоместных отношений – таблицы, например, таблицы, в которых содержатся сведения о персонале какой-либо
59