Полиномиальные алгоритмы решения переборных задач Стрыгин, Владимир Захарович

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

Актуальность темы. Кибернетику (инфс-рмгтику. счлцщ^г «си-пес) можно¹ определить как науку о Формах и алгоритмах представления, преобразования, сбора, хранения, поиска и передачи информации в естественных: и искусственных, биологических, технических и сопи альны'х системах, в частности информационных измерительных, поисковых, вычислительных, управляющих, экспертных интеллектуальных сие темах И системах искусственного (и естественного) интеллекта. Формы представления и алгоритмы преобразована информации непосредственно определяют сложность создаваемых систем и эффективность их функционирования. Это особенно относится к переборным (или комбинаторным) задачам (для которых пока не найдены алгоритмы реше ния. не содержащие в той или иной мере полгый перебор всех возмож ных вариантов), число которых последние тридцать лет непрерывно растет во всех областях человеческой деятельности и отсутствие эф Фективных (полиномиальных) алгоритмов решения которых стало суще стеенным тормозом в развитии научно технического прогресса.

Еще в юзі году Яблонским СВ. была выдвинута гипотеза о неустранимости полного перебора в таких задачах, как минимизация бу леьых функций, синтез минимальных контактных схем и схем из Функ цокальных элементов. Этими задачами занимались, в частности, Яблонский СВ., Журавлев Ю.И. и Лупгнов СБ. В ія7і году канадский математик Кук С.А. выдвинул гипотезу, а в і я 7 2 году американский математик Карп Р-М. доказал теорему о сводимости (эквивалентности) всех np полных (т.е. универсальных) переборных (или комбинатор ных) задач друг к другу. Гипотеза предполагает, что или все мг полные задачи имеют полиномиальный от длины входа алгоритм реше ния (F--NP), или ни одна из них такого алгоритма не имеет (p^np). Построение полиномиального на детерминированной машине Тьюринга

-ч-

алгоритма для любой из np-полных задач означает автоматическое построение таких алгоритмов для всех остальных np-полных задач. При этом np-полными назывались, в частности, задачи, которые можно сформулировать как задачи распознавания языков, или свойств множеств (с ответом "да" или "нет"), решаемые недетерминированной машиной Тьюринга за полиномиальное время. Первой np-полной задачей была задача выполнимости, или обратная ей задача определения общезначимости (тавтологичности) булевой формулы (Кук С.А). В і это году в книге "Вычислительные машины и труднорешаемые задачи 1":вве

ДЄНИЄ В ТЄОРИЮ NP-ПОЛНОТЫ]" (М.: МИР, 1982, 41GC) ЭМерИКЭНСКИе МЭ -

тематики Гэри М.Р. и Джонсон Д.С. развили теорию np-полноты и да ли формулировки трехсот np-полных задач.

Приведем набор коротких цитат иг этой книги: "Вопрос о том, действительно ли NP-полные задачи труднореіиае мы, в настоящее время считается одним из основных открытых вопро сов современной математики и теоретической кибернетики" (с2«). "NP-полнота задачи означает, что для ее решения полиномиальным ал горитмом требуется по крайней мере крупное открытие" (C28). "Сое ременные методы доказательства не достаточны ни для доказательст ва того, что p#np. ни того, что p-.np. эти методы бесполезны и для решения других открытых вопросов" (С231). "Для решения вопросов о взаимоотношениях между классами р и np, а также других классов языков, вероятно, требуются совершенно иные методы доказательства. В том случае, конечно, если вообще подобные вопросы можно решить" (C231). "По крайней мере в принципе, вопросы такого типа могут быть независимыми от теории множеств и. следовательно, неразрешимыми при использовании стандартных логических средств. Хотя авторы не так пессимистически смотрят на разрешимость вопроса о взаи моотношении классов р и np. никто не надеется, что этот вопрос бу

ДЄТ РЄШЄН В СКОРОМ времени" (C231).

-s-

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

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

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

разработка новой математической модели:

построение полиномиальных алгоритмов решения нескольких перебор пых задач в этой модели;

- построение абстрактной ЭВМ нового тип.і для решения переборных задач;

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

Научная новизна диссертации. Получен положительный ответ на один из основных открытых вопросов современной математики и теоре тической кибернетики (информатики) о существовании (возможности

- б -

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

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

Построены полиномиальные от п2^л (\"ч і . . . .'*) и от длины входа («04...7) по времени и памяти алгоритмы решения ряда np-полных пе реборных задач; і> минимизации полностью определенных булевых фун кций п переменных в дизъюнктивных нормальных Формах (о покрытии): 2) синтеза минимальных схем из Функциональных элементов И НЕ (Фун кций Шеффера); з) синтеза минимальных контактных схем: і) выявле ния общезначимости (выполнимости) булевых Формул: г>) о разложении булевой Функции на изолированные подфункции; о) о независимом мно жестве (рабочих наборов, не имеющих рабочих соседей); і) гюетрое ния и функционирования базы данных и знаний.

Построены классы булевых функций и их суперпозиций, имеющих полиномиальные степени 2...4 от т^п (сложность г,(и)<2^е/,г) алгорит мы минимизации: типа шахматная доска, разомкнутая и замкнутая тон кая и толстая цепь, метацепь (c(n )*(и2" f- ), плотных б.ф.(с(п)<2 ") и случайных ("почти всех") функций (с(н)<г ). Установлено, что не существует Функций сложнее плотных, а случайные б.Ф. являются

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

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

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

Установлено, что в предложение»'! мат<еі;-)тлчоекой модели матри чной логике ложными являются гипотеза Кука С А. (и теорема Кар па P.M.) о сводимости м' полных переборных задач друг к другу и гипотеза Яблонского С.В. о принципиальной неустранимости перебора в задачах минимизации булевых Функций, синтеза минимальных контак тных схем и схем из Функциональных злем<што;, а также широко рае пространенное мнение о том. что все np полные задачи не имеют по линомиальных алгоритмов решения.

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

кибернетике (информатике). Диссертация позволяет многим тысячам исследователей в различных областях науки и техники приступить к поиску (построению) полиномиальных алгоритмов решения своих переборных задач, зная, что такое решение принципиально возможно (в частности с использованием новой математической модели - матричной логики). а не ограничиваться признанием нерешабельности этих задач в результате их сведения к известным np-полным (т.е. универсальным) переборным задачам, как это до сих пор было в соответст вии с гипотезой Кука С.А. (и теоремой Карпа P.M.) о сводимости np' полных задач друг к другу, гипотезой Яблонского СВ. о принципи альной неустранимости перебора в некоторых переборных задачах и широко распространенным мнением о том. что все np-полные задачи действительно являются труднорешаемыми, т.е. не имеют полиномиаль ных алгоритмов решения.

Диссертация является теоретическим обоснованием необходимости и- возможности создания ЭБМ принципиально нового типа - комбинатор ной машины для решения полиномиальными и линейными от длины входа по времени алгоритмами двойных переборных задач, - которая явля ется новым направлением в развитии вычислительной техники.

Применение результатов диссертации позволяет повысить эФФек тивность интеллектуальных систем и систем искусственного иителлек та, в частности систем автоматизированного проектирования больших интегральных схем (БИС и СБИС) и машин баз данных и знаний.

Автор защищает:

і. Утверждение о существовании (возможности построения) полиномиальных алгоритмов решения переборных задач, или об устранимо сти перебора в дискретных экстремальных задачах, т.е. утверждение о ложности гипотезы Кука С.А. (теоремы Карпа P.M. и теории np-полноты Гэри М-Р. и Джонсона Д.С) о сводимости np-полных (т.е. универсальных) переборных задач друг к другу, утверждение о ложности

гипотезы Яблонского СВ. о принципиальной неустранимости перебора в некоторых дискретных экстремальных задачах (минимизации булевых Функций, синтеза минимальных контактных схем и схем из функциона льнах элементов), а также утверждение о ложности широко рас-про страненного мнения о том, что все VP-полные переборные задачи дей ствятельно являются труднорешаемым.1, т.'З. не имеют полиномиальных алгоритмов решения.

2. Новую модель дискретной математики - матричну» логику, отк рывающую новое направление в Философии математики, обеспечивающую решение ряда переборных задач полиномиальными алгоритмами и вклю чающую в себя: новые аксиомы теории минимизации булевых Функций. исчисления высказываний, баз данныч. знаний и конечного исчисле ния предикатов, в том числе закон третього "г и не г" как основ ной закон мышления, сжатия информации и образования понятий; но вые нетрадиционные подходы, логические средства, формы представле ния и методы обработки информации, новое содержание основных поня тий математической логики (исчисления высказываний и предикатов) и оснований математики (теории множеств теории доказательств, те ори/ алгоритмов).

л. Полиномиальные от п2^п (No1...:m и от длины входа (Noi...7) по времени и памяти алгоритмы решения конкретных кг полных пере борных задач-. U минимизации полностью определенных булевых Функ ций п переменных в дизъюнктивных нормальных Формах (о покрытии)-. 2) синтеза минимальных схем из Функциональных элементов И-НЕ (Фун кциа ШеФФера); з) синтеза минимальных контактных схем: 4) выявле ния общезначимости (выполнимости) булевых Формул; 5) о разложении булэвой Функции на изолированные подфункции,- в) о независимом множестве (рабочих наборов, не имеющих рабочих соседей); 7) построе ния и функционирования базы данных и знаний.

4. Классы булевых функций и их суперпозиций, имеющих полиноми-

-ре-

альные степени г...4 от п2^п (сложность с{п)<г^Чп) алгоритмы минимизации: типа шахматная доска, разомкнутая и замкнутая тонкая и толстая цепь, метацепь (с(n)*n²-2^irl) . плотных функций Васильева К). Л. (c(n)<2^v,!) и случайных ("почти всех") Функций (с(п)<2 " ). Утверждение о том. что не существует функций сложнее плотных, а случайные б.ф. являются суперпозицией Функций типа шахматная доска и плотных б.ф. Универсальный алгоритм, который обеспечивает точное решение задачи минимизации практически любой б.ф. (для неизвестных б.ф. погрешность не превышает нескольких процентов) и определяет сложность и точность универсальных алгоритмов синтеза минимальных контактных схем и схем из функциональных элементов (Функций ШеФФера), описываемых булевыми Функциями.

5. Архитектуру, алгоритмы Функционирования и схемные решения ЭВМ принципиально нового типа - комбинаторной машины (КМ) для решения полиномиальными и линейными от длины входа алгоритмами двойных переборных задач, слишком сложных для их решения традиционными средствами, - которая открывает новое направление в развитии вычислительной техники.

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

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

8. примеры применения разработанных полиномиальных алгоритмов для решения конкретных переборных задач.

Апробация работы. Основные научные результаты диссертационной работы обсуждены на 9-й Всесоюзной конференции по проблемам теоре-

тической кибернетики в г-Волгограде в сентясре 1990Г,- на іі-й меж республиканской конференции по математической логике в г.Казани б -8 октября 1992Г: на з-й конференции по искусственному интеллекту

КИИ-92 В Г.ТВЄРИ 20-23 ОКТЯбрЯ 19Э2Г: На СИИП03ИУМЄ "МЄТОДЬІ ИСКУС

ственного интеллекта в компьютерах новых поколений" в г.Рязани в

Сентябре 1993Г; На МЄЖДУНЗРОДНОЙ Конференции. ПОСВЯЩеННОЙ 7 5-ЛЄ

тию ЦАГИ "Методы и средства экспериментальных исследований в аэро навтике" в г.Жуковском в ноябре 1ээзг; на кснФеренции "Искусствен ный интеллект в 2 1-м веке" в г.Калининграде Московской обл. в ок тябре-ноябре 1995Г: на 5-й конференции о м?ждународным участием "Искусственный интеллект КИИ-эг." в г.Казани в іяяг.г.; с ними озна комклись ведущие специалисты академии наук к высшей школы. Диссер тация рассмотрена руководством и специалистами ЦАГИ и научно тех ническим советом кафедры математической кибернетики МГУ.

Публикации. Основные результаты диссертации опубликованы и 17 статьях, докладах и тезисах конференций по теоретической кибернетике, математической логике, информатике, искусственному интеллек ту и его приложениям ( 1 . . . 1 7 ] .

Объем работы. Диссертация содержит 275 страниц, состоит из введения, четырех глав, заключения и приложений, в том числе п та блии, 17 рисунков. 7R наименований цитируемой литературы.