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

АКАДЕМИЯ НАУК РЕСПУБЛИКИ БЕЛАРУСЬ ИНСТИТУТ МАТЕМАТИКИ

УДК 519.854

НАЙДЕНКО Владимир Григорьевич

НЕКОТОРЫЕ ВОПРОСЫ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ И МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Минск-1997

Работа выполнена на кафедре автоматизированных систем управления Белорусского государственного университета информатики и радиоэлектроники

Научный руководитель кандидат технических наук,

доцент О.В. Герман

Официальные оппоненты доктор физико-математических

наук, профессор H.H. Метельский

кандидат физико-математических наук, доцент А.Е. Будько

Оппонирующая организация Белорусский Государственный

Университет

Защита состоится (рißppijjA 1997г. в часов на

заседании совета по защите диссертаций Д 01.02.02 в Институте математики АНБ по адресу: 220012, г. Минск, ул. Сурганова 11

С диссертацией можно ознакомиться в библиотеке Института математики АНБ

Автореферат разослан «№« 1997г.

Ученый секретарь

совета по защите диссертаций,

кандидат физико-математичеких наук

Л-™|^А°тровский А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Наиболее очевидный метод решения комбинаторных задач -поочередно перебрать все варианты решения и выбрать требуемый'. Однако, как правило, число вариантов очень велико и их просмотр потребовал бы больших затрат времени. Поэтому этот простой алгоритм не эффективен по времени и практически непригоден. Многие известные комбинаторные проблемы входят в класс ЦР-полных задач, поэтому маловероятно найти для них эффективные алгоритмы.

Острая практическая нувда в решении комбинаторных проблем заставляет искать пути преодоления трудностей, связанных с их решением. В качестве таких путей мокно отметить следующие : улучшение переборных алгоритмов за счет разумной организации пх работы, выделение эффективно разрешимых подклассов задач в обзей проблеме, разработка приближенных алгоритмов. Что касается улучшения организации работы переборных алгоритмов, то это позволило несколько расширить размерность решаемых задач, однако ситуация качественно не изменилась. Попытки выделить эффективно разрешимые подклассы из ГСР-полных задач не привели к сколько-нибудь значительным результатам. Особый интерес в классе 'приближенных методов представляют статистически эффективные алгоритмы.

Многие вопросы,касающиеся разработки эффективных алгоритмов для решения комбинаторных задач и оценки их вычислительной сложности, уже ' исследованы отечественными и зарубекнзми математиками. Отдельные аспекты данной проблемы широко освещены в работах М.Гэри, Д.Джонсона, С.Кука, Р.Ладнера, Ю.И.Журавлева, В.А.Йгаличева, М.М.Ковалева, М.К.Кравцова, В.И.Сарвановэ, Р". И. Тышкевич, Н.Н.Метельского, В.А.Мощенского, А.Е.Будько, А.Д.Закревского, Н.А.Лепешинского и др. Этими учеными внесен значительный вклад в разработку теоретических и методологических

вопросов вычислительной сложности.

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

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

Связь работы с крупными научными программами и темами. Диссертация выполнялась с 1991 по 1994 год на кафедре АСУ Белгосуниверситета информатики и радиоэлектроники в соответствии с плановыми научными исследованиями по теме: "Логические и эвристические методы синтеза управления в технических системах".

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

Научная новизна работы. Представлены новые результаты, касающиеся структуры класса Ш>, в частности показано, что при условии справедливости гипотезы Р * ИР не существует алгоритма, который бы для каждой задачи из ОТ устанавливал, принадлежит ли она к классу Р или нет. Класс конструктивных трансрекурсивных алфавитных операторов может быть не замкнут относительно операции композиции при некоторой непрерывной хаусдорфовой топологии на пространстве слов. Доказан ряд теорем по корректности, сходимости и трудоемкости алгоритмов, которые легли в основу статистически-эффективных методов решения некоторых комбинаторных проблем.

Практическая значимость. Полученные теоретические результаты, касающиеся алгоритмической неразрешимости некоторых свойств классов ГО* и Р, могут быть использованы при оценки относительной сложности задач из ЫР. Разработанные вычислительные методы дают возможность значительно ускорить решение комбинаторных задач, что существенно снижает временные затраты и повышает эффективность использования вычислительных средств. Программа, разработанная на базе новых методов, позволяет быстро решать задачи о покрытии большой размерности на персональных ЭВМ. Идеи доказательства статистической эффективности разработанных методов решения комбинаторных задач могут быть применены в дальнейших исследованиях при построении и обосновании новых методов дискретной оптимизации.

Эконоиическая значииость. Оценить экономическую значимость результатов диссертации на данном этапе не представляется возможным.

Основные положения диссертации, выносимые на защиту:

1. Новые свойства классов Ж1 и Р.

2. Топология конструктивных трансрекурсивных алфавитных операторов.

3. Статистически эффективные алгоритмы для решения комбинаторых задач о покрытии, независимом множестве графа, выполнимости К® и поиска в пространстве состояний.

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

Апробация основных результатов. Материалы диссертации докладывались на научно-практической конференции по искусственному интеллекту (г. Туапсе), на научной конференции студентов, молодых ученых и аспирантов в БГУИР, а также на научных семинарах в Институте математики АНБ. Программа по решению задач о покрытии на основе разработанных методов принята в фонд алгоритмов и программ АН РБ с регистрационным номером 00679-

Опубликованность результатов. Основные результаты диссертации опубликованы в 11 работах.

Структур3 работы. Диссертация состоит из введения, общей

характеристики работы, • четырех глав, выводов, списка

использованных источников (76 наименований) и приложения. Работа

изложена на 97 страницах машинописного текста, содержит 2 таблицы и 12 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Каждой контекстно-свободной грамматике С с основным алфавитом Е сопоставим язык (Е*\Ь(С))#Ьыр :

(Е*\Ь(С))#1нр = { х#у | х е Е*\Ь(С) , у е Ьыр , # е Е } ,

где Е = {0,1} - алфавит о символами 0 и 1; * - новый символ, не принадлежащий к Е; Ьщ, обозначает некоторый фиксированный

ЫР-полный язык над алфавитом Е.

*

Для языков вида (Е МСО)#Ь доказаны теоремы 1.1 и 1.2.

*

Теорема 1.1. Язык (Е \Ь(0)#Ьнр принадлежит классу №Р.

Теорема 1.2. При условии ИР * Р, язык (Е*\Ъ(С))#Ьмр принадлежит классу Р тогда и только тогда, когда Ь(С) = Е*.

Из теорем 1.1 и 1.2 вытекает следующая теорема.

Теорема 1.3. Не существует алгоритма, который бы относительно произвольной полиномиальной недетерминированной машины Тьюринга выяснял : принадлежит ли распознаваемый ею язык к классу Р или нет.

Следствие. Алгоритмически неразрешимы также следующие вопросы: является ли Ш>-полным язык, распознаваемый заданной полиномиальной недетерминированной машиной Тьюринга; имеет ли место Ь(Т4) о< Ь(Т2) для заданных полиномиальных недетерминированных машин Тьюринга Т1 и 1г.

Это означает, что в классе МР существуют такие задачи, принадлежность которых к классу Р невозможно гарантированно

определить (то есть за конечное время, пользуясь формальными методами).

Кроме того, показано, что проблема определения принадлежности к классу Р языка, распознаваемого заданной НПМТ,

*

трансполуразрешима. Далее на пространстве слов из Е введена метрика р:

0 , если р = ч;

, если р = 1п0т\ (I = 1п0и2, т^т2, п, т , т2 е Ы;

если р е ОА , ч = 1п0т , р(п) = р, п,т е И;

1 , во всех остальных случаях

где р,ч слова из Е ; N - множество натуральных чисел; А -дополнение некоторого Е3[Н]-простого множества; р - биекция из N в ОА. Символ Н обозначает полное рекурсивно перечислимое подмножество Е , а Ез[Н]-простые множества это те, которые не содержат бесконечных подмножеств, рекурсивно перечислимых в Ез[Н].

Для топологии т метрики р доказана следующая теорема.

Теорема 1.6. Существует топология Т, при которой класс трансрекурсивных конструктивных алфавитных операторов не замкнут относительно операции композиции.

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

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

Р(Р,<1)=Р(а,Р) =

1 1 + Ы

1

к! '

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

Правило порождения нового отсекающего столбца. Пусть К - верхняя оценка мощности минимального покрытия, то есть К> |Пт:|:п1, где Пт1п - минимальное покрытие матрицы Вп .

Выберем произвольно К столбцов ___, ^ из матрицы Вп т.

Столбцы выбираем так, чтобы строки, содержащие менее

двух единиц каждая в указанных столбцах, образовывали покрытие

* $

матрицы Вп т. Построим новый столбец J следующим образом: Л содержит "1" в строке 1 тогда и только тогда, когда как минимум два столбца из С^^,...,^} содержат в 1 "1". В противном случае j содержит "О" в строке 1. Справедливы следующие теоремы:

Теорема 2.1. Если существует покрытие для исходной матрицы с мощностью меньше К , то любое такое покрытие исходной матрицы покрывает и новый отсекающий столбец.

Теорема 2.2. Столбец-отсечение j гарантированно не доминирует над каким-либо другим столбцом, если участвующие в порождении столбцы ^ , ... ,^ выбираются следующим образом. Пусть П={Х1,...,Х1) > к } - неизбыточное покрытие , тогда только

строка Ц содержит "1" в столбце ^ , а строки ,

имеют "О" в том же столбце, только ^ содержит "1" в столбце

¿2 » а строки Х1,...Дк_1 - "О" и т.д.; только строка Х^

содержит в столбце "1й, а строки Х^..., - "О".

Теорема 2.3. Нахождение столбца-отсечения с минимальным количествам единичных элементов является ИР-трудной задачей.

Под плотностью р^ единиц в столбце 1 будем понимать отношение числа единиц в столбце 1 матрицы Вп к п .

Для заданных натуральных чисел т, п и рациональных чисел Р-|,...,Рга £ [0,1] обозначим множество всевозможных (0,1)-матриц размерностью п строк и т столбцов через К(п,ш,р1,...,рт) , и каждая матрица в своих столбцах 1,...,га имеет плотности единичных элементов р1,...,рт соответственно.

Рассмотрим следующую задачу: если матрица Вп выбирается случайным образом из К(п,т,р^,...,рт) так, что вероятность

выбора произвольной матрицы равна 1/|К(п,т,р1,... ,рт) |, где

|К(п,т, р1Г...,рт )| - мощность множества К(п,т,р1,...,рт), то

какова вероятность того, что в матрице Вд ш существует хотя бы одно покрытие из к строк?

Математическое ожидание общего числа покрытий мощностью в К строк имеет вид:

^к=Сп Л/1-^ (2'1)

Е,, определяется следующим образом:

Р*П Р+П РЛ1

» —X1' ""¿Г ) (2-3)

^к = если П_Р£П < ^ )

*

Воспользуемся следующей оценкой д^ : "к =

*

Если показать, что < 1, тогда с вероятностью ошибки

0.003 можно утверждать, что Х^ =0, то есть что в матрице нет покрытий с К строками.

Вернемся теперь к итерационной схеме решения ЗМП. Если на

некоторой итерации 1 окажется, что в матрице Вд т имеется

*

лучшее из найденных покрытий из К+1 строки, и < 1 , то с вероятностью ошибки 0.003 это покрытие является оптимальным

и процесс решения прекращаем. £

• Если > 1 , то добавляя новые столбцы, выйдем на более

*

лучшие решения, либо ц^ станет меньше 1.

Можно показать, что число добавленных столбцов, а значит

п-т-р

число итераций алгоритма, не превосходит в среднем О

У 1-р

По быстродействию превосходство данного алгоритма достигает 50-100 раз по сравнению с методом ветвей и границ или алгоритмом Джеффриона.

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

Многие комбинаторные задачи можно интерпретировать как

'-- I '

1-Р )

задачу поиска максимальной нулевой квадратной подматрицы ВО симметричной (0,1)-матрицы'В с нулевой главной диагональю, представленной в третьей главе. В ВО множества строк и столбцов совпадают. Обозначим через b множество индексов строк (столбцов) произвольной нулевой подматрицы В, а через R(b) -

Л/ |-V£

число элементов в Ь. Нас интересует множество b с

максимальной величиной R(b ).

Если B(1,J)=1, то назовем строки i и J (столбцы i и j) несовместными. Пусть даны две несовместные строки i и j. Будем говорить, что строка i покрывает строку J, если в каждом столбце K*i и K*J , где B(j,K)=1, имеет место В(1,К)=1.

Для решения задачи используем теоремы, формулируемые ниже.

Теорема 3.1. Если строка i содержит одни нули, то она

входит в Ь* .

Теорема 3.2. Если строка 1 покрывает строку j , то строку и столбец i можно вычеркнуть без потери решения из исходной (0,1)- матрицы.

Теорема 3.3. Пусть известно некоторое текущее решение

b и Й(Ь), где b определяет некоторую нулевую подматрицу исходной (0,1)-матрицы. Тогда из исходной (0,1)-матрицы можно без потери решения удалить все те строки и столбцы, которые содержат число нулей, меньшее, либо равное R(b) .

Теорема 3.4. Если каждая строка (0,1)-матрицы содержит ровно две единицы, то без потери решения можно удалить любую из строк.

Теорема 3.5. Пусть некоторая строка i содержит только две единицы в матрице В на пересечении со столбцами, скажем J1 и J2- Если при этом строки J.j и ¿2 несовместны между собой, тогда без потери решения можно удалить из матрицы В строки (столбцы) J1 и J2 .

Теорема 3.6. Пусть в В имеются К одинаковых строк, содержащих L единиц в столбцах J^ , где L < К, тогда

строки и столбцы Jj,..., J^ без потери решения удалить из В.

Понятие базовой структуры. Пусть 1 - строка, которая может быть удалена из В без потери решения. Удаление строки i назовем детерминированным, саму строку i - D-строкой, а множество D-строк - D-множеством, или просто D. Случаи детерминированного

удаления строк и столбцов определяются в приведенных выге теоремах 3.1-3-6. Ясно, что если В путем только детерминированных удалений "разваливается" до нулевой подматрицы ВО, то ВО и есть максимальная нулевая подматрица.

Допустим, что в текущей матрице В нет Б-строк. Тогда выбор удаляемой строки назовем недетерминированным, саму строку -И-строкой, а множество Н-строк - ^множеством, или просто N. Базовой структурой называется тройка

где Ь^ в - нулевая подматрица,полученная из В путем удаления строк и столбцов из N и Б .

Процедура решения. Пусть дана матрица В, причем Б=0. В качестве И-строки используем строку, содержащую максимальное число единиц. Последовательно удаляем И- и В-строки для получения базовой структуры; Б-строки удаляются в первую очередь. Пусть известна базовая структура и N={1^,— »п^Ь

С={сЦ,...,йу}, ^ ,...,Ь2}. Построим матрицу л со строками

Ьдо р и столбцами N. На пересечении строки Ь^ и столбца п^ поставим единицу, если в матрице В строки п^ и г^ несовместны. Назовем подмножество р строк матрицы Л покрытием, если для каждого столбца матрицы Л найдется какая-нибудь строка в р , содержащая в етом столбце "1". Если в л существует нулевой столбец .г,- то строку J можно ввести в Ъ^ ^

Теорема 3.9. Пусть р - неизбыточное покрытие для матрицы л, соответствующей структуре <М,Б,ЬМ с> . Тогда если

существует максимальная нулевая подматрица Ъ при которой

Н(Ь*)Ж(ЬЯ в), то ре Ь*.

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

Вариант А. Покрытие р содержит единственную строку а. Этот вариант дает возможность исключить из В строку а.

Вариант Б. Покрытие р содержит ровно две строки, а и р. В этом случае на пересечении строки а (строки р) и столбца 0 (столбца а) поставим 1.

Вариант В. Покрытие р содержит более двух строк. Пусть р={а1,«2,...ак}, к>2. Введем в исходную матрицу В

дополнительные строки (столбцы) ___'^к-Т Удовлетворяющие

следующим свойствам: каждая строка несовместна со строкой р ^,

1=1,к-1; каадая строка ¡3^ несовместна с теми строками из исходной матрицы В, с которыми несовместна строка а^; строки —>0^-1 попаРно несовместны друг с другом. Из полученной матрицы вычеркнем строку (столбец) а,^. В дальнейшем, при нахождении новой нулевой подматрицы, содержащей одну из строк строка будет интерпретироваться как строка

а^, ■ при этом, очевидно, что получение старой комбинации

исключается.

Математическое ожидание числа нулевых подматриц с размером в К строк (К>0) . для случайно выбранной (0,1)-матрицы Вп по равномерному вероятностному распределению из' класса всех (0,1)-матриц с размерами пхп и фиксированным отношением р количества нулей к общему числу элементов в матрице определяется по формуле

р(К)=с£ ехр(с| 1п р).

Итак, данное описание завершим констатацией следующих результатов. Пусть 1 - номер итерации алгоритма, в начале 1=1.

1. Для итерации 1 отыскиваем базовую структуру <11,Б,Ъ^

2. Если д(К) > 1/12, где К - порядок наибольшей нулевой подматрицы среди найденных на предыдущих итерациях1 нулевых подматрицах, то модифицируем матрицу В, вводя новые строки, для чего необходимо следующее:

а) найти матрицу л и любое ее неизбыточное покрытие р ;

б) исключить комбинацию р , как описано выше;

в) 1:=1+1, переход к шагу 1.

Если ¿1(К) < 1/12, то алгоритм завершается, причем наибольшая подматрица среди найденных на каждой итерации будет максимальной с вероятностью 0.05.

Предложенный алгоритм достаточно эффективен, поскольку в среднем количество его итераций составляет 0(1п ц), где ц -математическое ожидание числа максимальных нулевых подматриц. Вероятность потери решения очень мала. Выйгрыш в быстродействии по сравнению с известными алгоритмами Джеффриона .или Балаша - в отдельных случаях в несколько десятков раз, а для разреженных

больших (0,1)-матриц может быть больше.

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

Пусть г,к,п1,...,пк - натуральные числа перечисление всех булевых переменных. Определим

вероятностный устанавливать

и

'""

п»

К(п1,...,пк,г) = СР | Р = & V а±л }

1=1

где а^ е Ар={р1,р1,р2,р2,...,РГ,РГ}.

Случайный выбор формулы из К(п1,...,пк,г)

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

к п (р„ „ ~ = &

можно

Ч'

4,1 Х11г 1=1

Математическое ожидание числа интерпретаций, при которых

случайная формула (рг равенством

является истинной определяется

п

1

к 2-1 = 2Г- и " 1=1

п*

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

Рассмотрим теперь общую схему для представления задач,

называемую пространством (деревом ) состояний Ш-

*

Теорема 4.2. Пусть алгоритмом А с эвристической

А

функцией Ь. найден путь р со стоимостью Ср. Тогда вероятность

в 1+К0 раз превысит стоимость

того, что Ор не более чем

оптимального пути, не превосходит величину ¿¡(К)1' для каждого К=1,2,... , где N - общее количество закрытых вершин в дереве Т.

ВЫВОДЫ

Результаты проведенных исследований позволяют сделать следующие выводы:

1. При справедливости гипотезы Р * ИР, не существует

алгоритма, который по любой заданной проблеме из класса ГСР определял бы, принадлежит ли она к классу Р или нет. Отсутствие такого алгоритма свидетельствует о том, что в классе ИР существуют задачи, принадлежность которых к классу Р невозможно доказать средствами достаточно сильной формальной теории ( в частности, арифметики Пеано).

2. Найдена топология Т, при которой класс трансрекурсивных конструктивных алфавитных операторов не замкнут относительно операции композиции.

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

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

5. Программа на языке Т1ГОВ0 РАБСАХ 5.5, реализованная на основе статистически эффективных методов, позволяет решать задачи о минимальном покрытии большой размерности (до 500 переменных) за несколько десятков секунд на персональной ЭВМ АТ 286.

6. Разработан вероятностный критерий для проверки

выполнимости конъюнктивной нормальной фор/ы, который может

использоваться для эвристического усиления принципа

резолюций. Установлена новая вероятностная интервальная

оценка отклонения стоимости пути, находимого с помощью

ж

модификации алгоритма А Нильсона, к стоимости оптимального

пути. Достоинство данного подхода - это снятие' ограничения на

монотонность эвристической функции, характерного для алгоритма ж

А , что позволяет расширить область применения данного алгоритма.

По теме диссертации опубликованы следующие работы

1. Герман 0.В.,Германович Е.И., Найденко В.Г. Решение задач в инструментальной расчетно-логической системе "X" : Тезисы доклада на всесоюзной конференции "Интеллектуальные системы".-Туапсе, 1991.- 0.15-16.

2. Герман О.В., Германович Е.И., Найденко В.Г. Высоко параллельный алгоритм логического вывода: Тезисы доклада на всесоюзной конференции "Интеллектуальные системы".- Туапсе, 1991.- с.17-18.

3. Герман О.В., Германович Е.И., Найденко В.Г. Логический вывод в системе, использующей отношение несовместимости. //Сборник рефератов деп. рукописей.- М.: ВИМИ, 1991.- вып. N8.-18с.

4. Герман О.В., Германович Е.И., Найденко В.Г. Алгоритм булевой оптимизации на (0,1)-матрицах //Ж. вычисл. математики и матем. физики.- 1992.- N 7.- с.1113-1125.

5. Птичкин В.А., Герман О.В., Найденко В.Г. Об эвристическом усилении метода резолюций // Автоматика и вычислительная техника.- Мн.: Вышейш. школа, 1993.- вып 21.- с.88-93-

6. Герман О.В., Найденко В.Г." Статистически-эффективный алгоритм для решения задачи о минимальном покрытии//Экономика и математические методы.- 1993.- т.29, N4.-с.138-149-

7- German O.V., Germanovich Ye Л., Naidenko V.G. Boolean optimization algorithm for (0,1)-matrices // Comput. Maths.Hath. Phys.- Pergamon Press Ltd, 1993.- pp.995-1005.

8.Герман O.B., Найденко В.Г. Улучшенный алгоритм А Нильсона на основе вероятностной эвристической функции //Автоматика и вычислительная техника.- Мн.,1994.- вып. 22.-с.73-79.

9. Герман О.В., Найденко В.Г. Программа GN для решения задачи о минимальном покрытии //РФАП Ali РБ.- 1994-- If 00679.

10. Найденко В.Г. К проблеме Р =? NP //Доклада АН /Российская Академия.- 1996.- т.348,N6.- с.731-732.

11. Найденко В.Г. Проблема композиции конструктивных трансрекурсивных операторов //Доклады АН /Российская Академия.-1996.- t.349,N1.- с.20-21.

РЕЗШЕ

Найденко Владимир Григорьевич "НЕКОТОРЫЕ ВОПРОСЫ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ И МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ"

Ключевые слова: машина Тьюринга, вычислительная сложность, проблема Р =? ИР, комбинаторная проблема, пространство состояний, статистически-эффективный алгоритм

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

теории вероятностей и математической статистики, принцип метода

*

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

• РЭЗЮМЕ Найдзенка Уладз1м1р Рыгорав1ч , "НЕКАТОРЫЯ ПЫТАНН1 ВШПЧАЛЬНАЯ ЦФККАСЦ1 I МЕТАДЫ РАШЭННН КАМБ1НАТОРНЫХ ЗАДАЧ"

Ключавыя словы: машына Цюрынга, выл!чальная цяжкасць, праблема Р =? ГСР, камб!наторная праблема, прастора станау, статыстычна-еффектыуны алгарытм

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

статыстык!, прынцып метада адрезау, метад рвзалюцы! Раб1нсона, *

алгарытм Шльсана А пошуку у прасторы станау, метад рэдукцы!. Прадстаулены новыя вын1к! адносна структуры класса №Р, асаб!ста паказана, што пры ул!ку г!потэзы Р * ИР не 1снуе алгарытма, як! б дзеля кожнай задачы з ИР рашау, уваходз1ць яна у клас Р ц! не. Клас канструктыуных трансрэкурс1уных алфав1тных аператарау мозка быць на замкнуты адносна аперацы! кампаз1цы! пр! некаторой неперарыунай тапалогН на прасторы слоу. Даказаны рад теарем по прав!льнасц1, сходнасц! 1 цяжкасц! алгарытмау, як!я лягл! у аснову статыстычна-еффектыуных метадау рашвння некаторых камб!наторных праблем.

■ SUMMARY Naidenko Vladimir Grigorevich "SOME QUESTIONS OP COMPUTATIONAL COMPLEXITY AND METHODS POR SOLVING COMBINATORIAL PROBLEMS"

Keywords: Turing machine, combinatorial problem, computational complexity, the P =? NP problem, space of states, statistically efficient algorithm

The researoh objects of this paper are. combinatorial

problems known as the set covering problem, problem of finding

the maximum zero square submatrix of simmetric boolean matrix

with zero main diagonal, SAT-satisfaction and problem of

estimation of computational complexity. Main purpose of the

research is to solve the question on the existance of a

recursive procedure of establishing the real computational

complexity of combinatorial problems, and is to develope the

more efficient methods (than existing ones) for solving the

combinatorial problems. The methods of theory of probability, a

principle of the severance methods, Robinson's resolution

x

methods, Nilson's algorithm A on a search space, the reduction methods are used. New results of the structure of class NP are obtained. Namely it is established that there cannot be any algorithm that determinates membership of a problem from NP in P. The class of constructive transrecursive alphabet operators may be unclosed under the operation of composition with some topology on a word space. Many theorems on the validity, convergence and computational complexity of the algorithms that lie in the foundation of statistically efficient methods for solving some combinatorial problems have been proven.