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

ВВЕДЕНИЕ.

ГЛАВА I. Алгоритмическая сложность задачи выразимости . 10 в многозначных логиках.

§ I.I. Описание и анализ сложности алгоритма . 10 решения задачи выразимости в алгебре логики.

§ 1.2. HP -трудность задачи выразимости . . 24 в Рк, (Ьь).

ГЛАВА П. Метод построения быстрых алгоритмов . . 55 в ^-значной логике.

ГЛАВА Ш. Алгоритмическая сложность задачи . . .67 распознавания полноты в f^lc

Одной из ветвей математической логики является многозначная логика, которая в последнее время бурно развивается. Быстрое развитие многозначной логики связано с тем, что во многих областях науки и техники стали возникать задачи, для описания и решения которых потребовался аппарат математической логики с высказываниями, принимающими более двух значений. Первой работой, в которой в наиболее полной форме были, освещены результаты, относящиеся к функциональным построениям в многозначной логике, была работа [2l] .

Многозначная логика изучает множество Pit всех функций Кос.11) : Ек , где Ek = {0,i,.,M,

Однимих из важных задач, возникающих в теории функций h -значной логики [ k ^ £) , являются задача о возможности выразить некоторую функцию ^ Рк, через функции системы x^ePk, , Ui,М. , посредством операции суперпозиции, а также задача распознавания полноты системы функций из Pit . Сразу заметим, что вторая задача является, в некотором смысле, частным случаем первой задачи, поскольку сводится к задаче о возможности выразить некоторую функцию Шеффера в

Рк через функции системы

Обе задачи часто возникают в приложениях k -значных логик, например, в теории управляющих систем задача распознавания выразимости эквивалентна задаче о возможности синтеза некоторой функции (ос*'0) в конечном неполном базисе

1, fc(xai)f а задача распознавания полноты эквивалентна задаче о возможности синтеза произвольной функции в некотором базисе

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

Известно, что задача распознавания полноты в Рк алгоритмически разрешима [24] . Алгоритмическая разрешимость . задачи распознавания выразимости в Рк следует из несложного обобщения алгоритма распознавания полноты в

Рк , описанного в [24] . Однако оба алгоритма являются алгоритмами переборного типа, имеющими высокую временную сложность.

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

Американским математиком Э. Постом в [2?] была описана структура всех замкнутых классов в Р^ . Этот результат позволяет свести задачу распознавания выразимости в Рд к задаче распознавания принадлежности функций из

Ри различным замкнутым классам.

А.В.Кузнецов в [il] доказал, что существует конечная система замкнутых классов в Pit , каждый из которых целиком не содержит ни одного из остальных классов этой системы, такая, что система функций из полна тогда и только тогда, когда она целиком не содержится ни в одном из этих классов. Такие классы называются предполными. Э.Постом в работе [27] были построены все предполные классы в Рд, . В работе С.В.Яблонского [20] была описана система всех предполных классов в ра, . Некоторые семейства предполных классов в Pit были построены А.В.Кузнецовым и С.В. Яблонским и подробно описаны в[21] . Затем В.В.Мартынюк, JIo Чжу-кай, Пан Юн-цзе, Ван Сян-хао, Лю Сюй-хуа и Е.Ю.Захарова [2,8,12-I?] построили другие семейства предполных классов. Окончательно, И. Розенберг описал систему всех предполных классов в р^ в работе [28]. Таким образом, задача распознавания полноты в Рк, сводится к задаче распознавания принадлежности функций из Р|с, предполным замкнутым классам, описанным в [28]. Число всех предполных классов в Р^ было оценено в [9]. В.Б.Кудрявцев в [ю] рассмотрел задачу распознавания полноты системы функций, состоящей из одной функции. Им было показано, что для этого достаточно решить задачу распознавания принадлежности этой функции лишь для части предполных классов в

Определение. Будем говорить, что функция ^ (х' сохраняет предикат R (^эс, ) • Ёк^^Ед, > если для любых Ь наборов oLj^ (oUi^dlia,,. ? <Ltrb) (l=1v,Д)справедлива импликация

1)

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

- б

Все замкнутые классы в Р^ , а также все предполные классы в pjc предикатно описуемы.

Обычный переборный алгоритм распознавания принадлежности функции классу сохранения предиката RH . основанный на переборе всевозможных выборок из It*1' наборов значений переменных функции ^(x^) по t наборов, позволяет получить алгоритмы распознавания выразимости в til и полноты в "Р^ менее сложные, чем алгоритм, описанный в [24J. Однако и здесь, отказавшись от перебора, можно строить существенно более быстрые алгоритмы.

Р.М.Фрейвалдом была изучена сложность распознавания полноты в Рл на машине Тьюринга. Этот результат описан в работе [l9j . В работах [б] и была изучена алгоритмическая сложность задачи распознавания выразимости в Рк, , а в работе - алгоритмическая сложность задачи распознавания полноты в Р^ на машине с произвольным доступом к памяти [i].

Данная работа посвящена построению быстрых алгоритмов распознавания выразимости и полноты в Рк (к >2) , в ней также будет рассмотрена задача построения эффективных алгоритмов распознавания принадлежности функций из Pic предикатно описуемым замкнутым классам.

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

Nl=k 1,(Иа + 1) элементов из Efc и, следовательно, мощность полной входной информации задачи распознавания выразимости в будет равна м, m , Yi; / \

N = ZNt = 2k ,

1=0 а задачи распознавания полноты элементов из Dk, .

Под временной сложностью алгоритма понимается зависимость числа шагов, затрачиваемых алгоритмом на решение задачи, от размера входной информации. Будем считать, что алгоритмы реализуются машинами с произвольным доступом к памяти [ij. При этом будем использовать логарифмический весовой критерий стр.2з] , то есть будет оцениваться число операций, производимых алгоритмом над битовой информацией. Так как всюду в дальнейшем k считается фиксированным и оценки сложности алгоритмов рассматриваются с точностью до постоянного множителя, то вместо операций над битовой информацией можно рассматривать число операций над элементами из

Efc.

Большинство дискретных задач допускает решение с помощью алгоритмов переборного типа. Однако временная сложность таких алгоритмов, вообще говоря, экспоненциальна относительно мощности входной информации. Для некоторых задач этого типа удаётся построить эффективные алгоритмы, существенно более быстрые, чем алгоритмы полного перебора, однако таких задач мало. Естественно, возникает вопрос - можно ли при создании алгоритмов решения дискретных задач исключить перебор, или существуют задачи, для которых это принципиально невозможно. До настоящего времени эта проблема остаётся открытой. Ряд результатов указывает на то, что по всей видимости существуют задачи, в которых перебора избежать нельзя. Одним из первых результатов в этом направлении был результат С.В.Яблонского [22] .

В 1971 году появилась работа С.Кука , в которой был определён класс задач "NP . В этот класс входят такие задачи, в которых результат может быть только двух типов: либо "да", либо "нет", причём если ответ в задаче "да", то существует алгоритм доказательства этого факта с полиномиальной временной сложностью. Большинство задач, встречающихся на практике, после переформулировки их в виде задач с ответами "да", "нет" попадает в класс КР . С.Кук также показал, что одна конкретная задача, называемая задачей выполнимости, обладает тем свойством, что если она может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима. Такие задачи сейчас называются J\[P -трудными задачами.

С.Кук подчеркнул важность понятия "сводимость за полиномиальное время". Если одна задача с помощью алгоритма с полиномиальной временной сложностью сводится к другой, то любой полиномиальный алгоритм решения второй задачи может быть превращён в полиномиальный алгоритм решения первой. Основываясь на сводимости за полиномиальное время С.Кук доказал NP -трудность нескольких комбинаторных задач.

Вслед за этим Р.Карп. [22] доказал NP -трудность целого ряда хорошо известных дискретных задач. В настоящее время известно уже несколько сотен NP -трудных задач и ко -личество их быстро растёт.

Большой объём работы, проделанный в поисках алгоритмов, решающих NP -трудные задачи за полиномиальное время, даёт основание считать, что таких алгоритмов не существует, хотя в строгом смысле это до сих пор не доказано. Поэтому, если математик на практике сталкивается с NP -трудной задачей, наиболее разумно либо начать разработку эффективных алгоритмов, позволяющих решать различные частные случаи поставленной задачи, либо попытаться найти алгоритм, хотя и не гарантирующий быстрого решения в худшем случае, однако работающий быстро в большинстве случаев. Основные результаты теории сложности дискретных задач описаны в [i, 3, 1б] .

Данная работа состоит из трёх глав. Первая глава посвящена алгоритмической сложности задачи распознавания выразимости в Pit . В § I.I строится алгоритм распознавания выразимости в Р* с временной сложностью

В § 1.2 доказано, что при !с > Z эта задача является №

-трудной задачей, более того, она остаётся NP -трудной даже в случае 1

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

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

- в Р5 и Рб . В конце третьей главы доказывается теорема о существовании алгоритма распознавания полноты в Pic (к,^^4) существенно менее сложного, чем естественный алгоритм.

Все результаты, полученные в работе, конструктивны.

Автор искренне благодарен Валерию Борисовичу Алексееву за постановку задачи и большую помощь при её решении.

1. Дискретная математика и математические вопросы кибернетики. т. I. Под редакцией В. Яблонского и 0. Б. Лупанова. М., Наука, 1974.

2. Емельянов Н.Р. Об алгоритмической сложности задачи выразимости в многозначных логиках. В сб. Методы решения задач математической физики и их программное обеспечение, М., Издательство Московского Университета, 1984.

3. Емельянов Н.Р. Об алгоритмической сложности задачи распознавания полноты в г|с У1 Всесоюзная конференция по .проблемам теоретической кибернетики. Тезисы докладов. Саратов, Издательство Саратовского Университета.

4. Емельянов Н.Р. О сложности задачи выразимости в многозначных логиках. ДАН СССР

5. Захарова Е.Ю. Критерий полноты систем функций из 1г I t Проблемы кибернетики, вып. 18, М., Наука, 1967.

6. Захарова Е.Ю., Кудрявцев В.В., Яблонский С В О предполных классах в 1 -значных логиках. "ДАН СССР, 186, №3, 1969. с

7. Трахтенброт Б.А. Сложность алгоритмов и вычислений. Новосибирск, 1

8. Яблонский С В О функциональной полноте в трёхзначном исчислении. ДАН СССР, т. 95, I 6, 1

9. Яблонский С В Функциональные построения в Труды МИАН СССР, т. 51, 1958. к,-значной логике,

10. Яблонский С В Гаврилов Г.П., Кудрявцев В.Б,.Функции алгебры логики и классы Поста. М., Наука, 1

11. Яблонский С В Введение