Содержание к диссертации
Введение
ГЛАВА I. Алгоритмическая сложность задачи выразимости в многозначных логиках .
1.1.. Описание и анализ сложности алгоритма решения задачи выразимости в алгебре логики .
1.2. Nl -трудность задачи выразимости в Рк
ГЛАВА II. Метод построения быстрых алгоритмов в значной логике .
ГЛАВА III. Алгоритмическая сложность задачи распознавания полноты
Литература
- Описание и анализ сложности алгоритма решения задачи выразимости в алгебре логики
- Nl -трудность задачи выразимости в Рк
- Метод построения быстрых алгоритмов в значной логике
- Алгоритмическая сложность задачи распознавания полноты
Введение к работе
Одной из ветвей математической логики является многозначная логика, которая в последнее время бурно развивается. Быстрое развитие многозначной логики связано с тем, что во многих областях науки и техники стали возникать задачи, для описания и решения которых потребовался аппарат математической логики с высказываниями, принимающими более двух значений. Первой работой, в которой в наиболее полной форме были, освещены результаты, относящиеся к функциональным построениям в многозначной логике, была работа [2Ї] .
Многозначная логика изучает множество Г к, всех функ-
ций ${5?) Е— Ek , где Ёк = [0,1,...,И.
Одними из важных задач, возникающих в теории функций К, -значной логики [ К, ^
jL(x ^Єгк, і i=i,,...?Wl , посредством
операции суперпозиции, а также задача распознавания полноты системы
функций из lit . Сразу заметим, что вторая задача является, в некотором смысле, частным случаем первой задачи, поскольку сводится к задаче о возможности выразить некоторую функцию Шеффера в через функции системы
Обе задачи часто возникают в приложениях к -значных логик, например, в теории управляющих систем задача распознавания выразимости эквивалентна задаче о возможности синтеза некоторой функции je> \^СС ) в конечном неполном базисе
ШаЧМ*"*),.... Ыа"~)Ь
а задача распознавания полноты эквивалентна задаче о возможности синтеза произвольной функции в некотором базисе
В связи с вышесказанным, особый интерес представляет изучение поставленных задач с алгоритмической точки зрения.
Известно, что задача распознавания полноты в х к алгоритмически разрешима [24J . Алгоритмическая разрешимость . задачи распознавания выразимости в Г к следует из несложного обобщения алгоритма распознавания полноты в , описанного в [_24j Однако оба алгоритма являются алгоритмами переборного типа, имеющими высокую временную сложность.
Появление быстродействующих электронно-вычислительных машин усилило требования к алгоритмам, поскольку различные усовершенствования алгоритмов стали приносить существенный выигрыш во времени их работы. Поэтому, в настоящее время возникла необходимость построения алгоритмов решения задач распознавания выразимости и полноты в г (с возможно меньшей сложности. Отказ от сложных алгоритмов переборного типа потребовал при построении алгоритмов решения поставленных задач использовать более глубокие исследования в |С-значных логиках.
Американским математиком Э. Постом в [27 J была описана структура всех замкнутых классов в Г % . Этот результат позволяет свести задачу распознавания выразимости в Рд к задаче распознавания принадлежности функций из Г X различным
замкнутым классам.
А.В.Кузнецов в [її] доказал, что существует конечная система замкнутых классов в г It , каждый из которых целиком не содержит ни одного из остальных классов этой системы, такая, что система функций из fx полна тогда и только тогда, когда она целиком не содержится ни в одном из этих классов. Такие классы называются предполными. Э.Постом в работе j_27j были построены все предполные классы в Г % . В работе С.В.Яблонского [20] была описана система всех предполных классов в ра» Некоторые семейства предполных классов в г It были построены А.В.Кузнецовым и СВ. Яблонским и подробно описаны b[2IJ . Затем В.В.Мартынюк, Ло Чжу-кай, Пан Юн-цзе, Ван Сян-хао, Лю Сюй-хуа и Е.Ю.Захарова І2,8,12-І7І построили другие семейства предполных классов. Окончательно, И. Розенберг описал систему всех предполных классов в k в работе [28J. Таким образом, задача распознавания полноты в Хк, сводится к задаче распознавания принадлежности функций из j^ fc, предполным замкнутым классам, описанным в [28J. Число всех предполных классов в Р^ было оценено в [9J. В.Б.Кудрявцев в [iOj рассмотрел задачу распознавания полноты системы функций, состоящей из одной функции. Им было показано, что для этого достаточно решить задачу распознавания принадлежности этой функции лишь для части предполных классов в г It
Определение. Будем говорить, что функция 5 (аЧ є Pk
сохраняет предикат , если для любых Ь на-
боров оЦ = (oUi^cLijij»** j
Определение. Класс функций, сохраняющих предикат R(xj» будем называть классом сохранения предиката t\(5c /и обозначать 7(R)<
- б -
Все замкнутые классы в і% , а также все предполные классы в Ріс предикатно описуемы.
Обычный переборный алгоритм распознавания принадлежности функции дх*1) классу 2&(к) сохранения предиката R(x ) , основанный на переборе всевозможных выборок из к, наборов значений переменных функции j(pb ) по L наборов, позволяет получить алгоритмы распознавания выразимости в fz и полноты в }\ менее сложные, чем алгоритм, описанный в [24]. Однако и здесь, отказавшись от перебора, можно строить существенно более быстрые алгоритмы.
Р.М.Фрейвалдом была изучена сложность распознавания полноты в Гл на машине Тьюринга. Этот результат описан в работе [l9J . В работах [бJ и I 7J была изучена алгоритмическая сложность задачи распознавания выразимости в і к, , а в работе [б] - алгоритмическая сложность задачи распознавания полноты в Р^ на машине с произвольным доступом к памяти [ij.
Данная работа посвящена построению быстрых алгоритмов рас
познавания выразимости и полноты в , в ней также
будет рассмотрена задача построения эффективных алгоритмов рас
познавания принадлежности функций из г 1с предикатно описуемым
замкнутым классам.
Функции будут задаваться таблицами, в которых наборы значений переменных лексикографически упорядочены, а числа, входящие в таблицы, представляются своей двоичной записью. Для задания функции 5|(х L) потребуется таблица мощность которой равна ІН=к С*(И^L"^ 1) элементов из bit и, следовательно, мощность полной входной информации задачи распознавания выразимости в Р^ будет равна
N = ZNt = 2k >i+l) ,
1=0 l~0
а задачи распознавания полноты -
1-і - t^i
элементов из Dlt .
Под временной сложностью алгоритма понимается зависимость числа шагов, затрачиваемых алгоритмом на решение задачи, от размера входной информации. Будем считать, что алгоритмы реализуются машинами с произвольным доступом к памяти [ij. При этом будем использовать логарифмический весовой критерий Гі, стр.23] , то есть будет оцениваться число операций, производимых алгоритмом над битовой информацией. Так как всюду в дальнейшем к. считается фиксированным и оценки сложности алгоритмов рассматриваются с точностью до постоянного множителя, то вместо операций над битовой информацией можно рассматривать число операций над элементами из Ыс.
Большинство дискретных задач допускает решение с помощью алгоритмов переборного типа. Однако временная сложность таких алгоритмов, вообще говоря, экспоненциальна относительно мощности входной информации. Для некоторых задач этого типа удаётся построить эффективные алгоритмы, существенно более быстрые, чем алгоритмы полного перебора, однако таких задач мало. Естественно, возникает вопрос - можно ли при создании алгоритмов решения дискретных задач исключить перебор, или существуют задачи, для которых это принципиально невозможно. До настоящего времени эта проблема остаётся открытой. Ряд результатов указывает на то, что по всей видимости существуют задачи, в которых перебора избежать нельзя. Одним из первых результатов в этом направлении был результат С.В.Яблонского [22 J .
В 1971 году появилась работа С.Кука [25J , в которой был определён класс задач Иг . В этот класс входят такие задачи, в которых результат может быть только двух типов: либо "да", либо "нет", причём если ответ в задаче "да", то суще-
ствует алгоритм доказательства этого факта с полиномиальной временной сложностью. Большинство задач, встречающихся на практике, после переформулировки их в виде задач с ответами "да", "нет" попадает в класс ffP С.Кук также показал, что одна конкретная задача, называемая задачей выполнимости, обладает тем свойством, что если она может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима. Такие задачи сейчас называются ]\[г -трудными задачами.
С.Кук подчеркнул важность понятия "сводимость за полиномиальное время". Если одна задача с помощью алгоритма с полиномиальной временной сложностью сводится к другой, то любой полиномиальный алгоритм решения второй задачи может быть превращен в полиномиальный алгоритм решения первой. Основываясь на сводимости за полиномиальное время С.Кук доказал
-трудность нескольких комбинаторных задач.
Вслед за этим Р.Карп. Г22І доказал NF-трудность целого ряда хорошо известных дискретных задач. В настоящее время известно уже несколько сотен lu -трудных задач и ко -личество их быстро растёт.
Большой объём работы, проделанный в поисках алгоритмов, решающих N г -трудные задачи за полиномиальное время, даёт основание считать, что таких алгоритмов не существует, хотя в строгом смысле это до сих пор не доказано. Поэтому, если математик на практике сталкивается с -трудной задачей, наиболее разумно либо начать разработку эффективных алгоритмов, позволяющих решать различные частные случаи поставленной задачи, либо попытаться найти алгоритм, хотя и не гарантирующий быстрого решения в худшем случае, однако работающий быстро в
большинстве случаев. Основные результаты теории сложности дискретных задач описаны в [I, 3, I6J ,
Данная работа состоит из трёх глав. Первая глава посвящена алгоритмической сложности задачи распознавания выразимости в г к . В Ї.І строится алгоритм распознавания выразимости в г % с временной сложностью
В 1.2 доказано, что при K>Z эта задача является
-трудной задачей, более того, она остаётся -трудной даже в случае Wl= 1
Во второй главе описан общий метод, позволяющий строить эффективные алгоритмы распознавания принадлежности функций из fk предикатно описуемым замкнутым классам. Оцениваются временные сложности алгоритмов, получаемых этим методом, и приводятся примеры его применения.
В третьей главе рассматриваются задачи распознавания полноты в ГІС .На основе метода, описанного во второй главе, строятся линейные алгоритмы распознавания полноты в Р? » Рз и -М » и алгоритмы с временной сложностью
{-/(N'LO^NJ " в 15 и Г 6 .В конце третьей главы дока
зывается теорема о существовании алгоритма распознавания
полноты в существенно менее сложного,
чем естественный алгоритм.
Все результаты, полученные в работе, конструктивны. Автор искренне благодарен Валерию Борисовичу Алексееву за постановку задачи и большую помощь при её решении.
Описание и анализ сложности алгоритма решения задачи выразимости в алгебре логики
Под временной сложностью алгоритма понимается зависимость числа шагов, затрачиваемых алгоритмом на решение задачи, от размера входной информации. Будем считать, что алгоритмы реализуются машинами с произвольным доступом к памяти [ij. При этом будем использовать логарифмический весовой критерий Гі, стр.23] , то есть будет оцениваться число операций, производимых алгоритмом над битовой информацией. Так как всюду в дальнейшем к. считается фиксированным и оценки сложности алгоритмов рассматриваются с точностью до постоянного множителя, то вместо операций над битовой информацией можно рассматривать число операций над элементами из Ыс.
Большинство дискретных задач допускает решение с помощью алгоритмов переборного типа. Однако временная сложность таких алгоритмов, вообще говоря, экспоненциальна относительно мощности входной информации. Для некоторых задач этого типа удаётся построить эффективные алгоритмы, существенно более быстрые, чем алгоритмы полного перебора, однако таких задач мало. Естественно, возникает вопрос - можно ли при создании алгоритмов решения дискретных задач исключить перебор, или существуют задачи, для которых это принципиально невозможно. До настоящего времени эта проблема остаётся открытой. Ряд результатов указывает на то, что по всей видимости существуют задачи, в которых перебора избежать нельзя. Одним из первых результатов в этом направлении был результат С.В.Яблонского [22 J .
В 1971 году появилась работа С.Кука [25J , в которой был определён класс задач Иг . В этот класс входят такие задачи, в которых результат может быть только двух типов: либо "да", либо "нет", причём если ответ в задаче "да", то суще ствует алгоритм доказательства этого факта с полиномиальной временной сложностью. Большинство задач, встречающихся на практике, после переформулировки их в виде задач с ответами "да", "нет" попадает в класс ffP С.Кук также показал, что одна конкретная задача, называемая задачей выполнимости, обладает тем свойством, что если она может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима. Такие задачи сейчас называются ]\[г -трудными задачами.
С.Кук подчеркнул важность понятия "сводимость за полиномиальное время". Если одна задача с помощью алгоритма с полиномиальной временной сложностью сводится к другой, то любой полиномиальный алгоритм решения второй задачи может быть превращен в полиномиальный алгоритм решения первой. Основываясь на сводимости за полиномиальное время С.Кук доказал -трудность нескольких комбинаторных задач.
Вслед за этим Р.Карп. Г22І доказал NF-трудность целого ряда хорошо известных дискретных задач. В настоящее время известно уже несколько сотен lu -трудных задач и ко -личество их быстро растёт.
Большой объём работы, проделанный в поисках алгоритмов, решающих N г -трудные задачи за полиномиальное время, даёт основание считать, что таких алгоритмов не существует, хотя в строгом смысле это до сих пор не доказано. Поэтому, если математик на практике сталкивается с -трудной задачей, наиболее разумно либо начать разработку эффективных алгоритмов, позволяющих решать различные частные случаи поставленной задачи, либо попытаться найти алгоритм, хотя и не гарантирующий быстрого решения в худшем случае, однако работающий быстро в большинстве случаев. Основные результаты теории сложности дискретных задач описаны
Данная работа состоит из трёх глав. Первая глава посвящена алгоритмической сложности задачи распознавания выразимости в г к . В Ї.І строится алгоритм распознавания выразимости в г % с временной сложностью
В 1.2 доказано, что при K Z эта задача является -трудной задачей, более того, она остаётся -трудной даже в случае Wl= 1 Во второй главе описан общий метод, позволяющий строить эффективные алгоритмы распознавания принадлежности функций из fk предикатно описуемым замкнутым классам. Оцениваются временные сложности алгоритмов, получаемых этим методом, и приводятся примеры его применения.
В третьей главе рассматриваются задачи распознавания полноты в ГІС .На основе метода, описанного во второй главе, строятся линейные алгоритмы распознавания полноты в Р? » Рз и -М » и алгоритмы с временной сложностью В конце третьей главы дока зывается теорема о существовании алгоритма распознавания полноты в существенно менее сложного, чем естественный алгоритм.
Nl -трудность задачи выразимости в Рк
Таким образом, для решения задачи выразимости в достаточно для каждой функции из системы (Z) последовательно применить леммы 1.1., 1,4, 1,5, затем по лемме 1,6 получить замыкание системы (JL) , и наконец, используя следствие 1.1. решить вопрос о принадлежности функции замыканию системы (Z) . Общая сложность алгоритма не превосходит что завершает доказательство теоремы 1,1. Рассмотрим теперь задачу распознавания выразимости при Докажем сначала ГІГ -трудность этой задачи при fc - 3 и flt- i . Для этого полиномиально трансформируем в неё следующую задачу о точном покрытии, КР -трудность которой показана, например, в [і] . Дано множество So (U0ef) и система подмножеств этого множества Требуется выяснить, существует ли подсистема попорно непересекающихся подмножеств, являющаяся покрытием множества Ьо Множества будем задавать характеристическими векторами, то есть каждому множеству Si сопоставим двоичный вектор длины Ъ такой, что І -ый разряд этого вектора равен I тогда и только тогда, когда j -ый элемент множества So принадлежит множеству Si . Таким образом, размер задачи о точном покрытии будет равен И - "t \% + ±). Сопоставим системе подмножеств функцию , а множеству 2 о - функцию тогда и только тогда, когда существует точное покрытие множес тва ho множествами
При построе нии этих функций мы будем руководствоваться тем, что функция должна хранить в себе информацию о структуре всех подмножеств , а функция информацию о структуре самого множества Построение функций должно осуществляться за время, ограниченное полиномом от размера задачи о точном покрытии, следовательно, необходимо, чтобы эти функции содер жали не более чем по переменных Ш- размер задачи о точном покрытии) . Более того, строение этих функций должно позволить моделировать операцию объединения множеств пос. средством операции суперпозиции. Но операция суперпозиции является, в некотором смысле, более "широкой" операцией, чем операция объединения множеств, поэтому необходимо ограничить каким-либо образом применение операции суперпозиции. В данном случае это будет достигнуто построением функций Jo (х ) и ji. IpC J таких, что применение к функции Ji (ОС ) операции суперпозиции во всех случаях, кроме суперпозиций некоторого специального вида, будет приводить к функциям, из которых уже нельзя получить функцию jo \,оЬ ) . При суперпозициях же этого специального вида будет моделироваться операция объединения множеств таким образом, что функция тогда и только тогда, когда задача о точном покрытии имеет решение.
В качестве функции возьмём функцию, представ ленную в таблице, которая изображена на рисунке 2. Подмножес тва закодированы на группах наборов значений переменных этой функции, а на группах наборов \)о и $i+± кодируются пустые множества. Каждому из рассматриваемых множеств соответствует фиксирован ный набор \K0fl іУ Ц {L= Qyi,,,, 7 t) значений переменных состоящий из остальном единиц и iнулей. Эти наборы удовлетворяют условию K0AL 9 K A J при L S , а в выбираются произвольно. Таким образом, наборы KOptty задаются так, чтобы они были отличны друг от друга и позво ляли переводить один набор в другой перестановкой переменных количество которых выбирается так, чтобы их было достаточно для задания % + і кодов указанного вида . Далее будем считать, что Lj. t . При фиксированных значениях переменных 1,3 ,...,2 на группе наборов 6 кодируется структура подмножества bi следующим образом.
Метод построения быстрых алгоритмов в значной логике
Рассмотрим функцию -j (3Cj J . Она содержит УЬ переменных и , следовательно, хотя бы две из них не отождествлены ни с одной из свободных переменных функции j( E / Если мы положим любую из них равной нулю, а все остальные переменные положим равными единице, то функция J (Х0/ примет значение два.
Действительно, в этом случае наборы значений переменных для каждой из внутренних функций будут состоять из одной нулевой компоненты и других компонент равных единице. Из определения основных функций следует,что любая основная функция на наборах с одним нулём и остальными единицами принимает значения либо I, либо 2 (см. рис. 2) . Поэтому внутренние функции могут принять либо значение I, либо значение 2. Но тогда на месте переменных функции j ( ОС ) будет стоять либо набор, состоящий из одних единиц, либо набор, содержащий компоненту, равную ЇЙ ,: и, применив замечание 1.2, получим, что функция -J (х0 ) примет значение 2. Таким образом, функция обладает свойством 3 е функций типаї. Учитывая замечание 1.2, получаем, что в этом случае функция -С (ос, 0) является функцией типа I.
Пусть и функция подставляется в функцию вместо некоторой переменной, которая не является переменной ЗСо .
Положим переменную СС0 функции равной нулю, а все остальные переменные, входящие в функцию 5(:.) » равными единице. Тогда на вход внутренней функции \ ( i ) поступит некоторый набор, состоящий из одной нулевой и остальных единичных компонент, на котором она примет либо значение I, либо значение 2. Следовательно, на вход внешней функции j(x ) поступит набор, содержащий компоненту равную 2, либо набор (О, I, I, ... , I) , входящий в группу 1%) наборов значений переменных основной функции [см. рис. 2) и, следовательно, функция -С (хо) примет значение 2.
Среди переменных функции -V \OCij существует переменная, которая не отождествлена ни с одной из свободных переменных функции -V ( Х ) . Если положить её равной нулю , а все остальные переменные - равными единице, то внутренняя функция примет либо значение I, либо значение 2. Тогда либо все переменные внешней функции примут значение I, либо одна из них будет равна 2 и , следовательно, функция -V (jc j примет значение 2.
Таким образом, функция \ (3L 0 J обладает свойством 3 функций типа синие Учитывая замечание 1.2 получаем, что ив этом случае функция j (Х0) является функцией типа Пусть теперь функция ( i) подста вляется вместо переменной гХо Функции -j (х 1) и переменная ЭС-о функции j Х І j отождествлена с какой-нибудь свободной переменной функции
Если положить переменную Х0 внутренней функции равной нулю, а все остальные переменные - равными единице, то внутренняя функция примет значение 2, поскольку для неё это будет набор из группы наборов (Z) . Таким образом, на вход функции + (х поступит набор, содержащий компоненту, равную двум, и , следовательно, функция [Зс ] , а также и функция -у (pi0) , примут значение 2. Среди переменных внутренней функции j { Х х / найдётся переменная, не отождествлённая ни с одной из свободных переменных внешней функции з \JX J . Если положить её равной нулю, а все остальные переменные - равными единице, то функция xj) примет значение 2.
Таким образом, и при такого вида суперпозициях («Йо/ является функцией типа 4. Рассмотрим теперь случай, когда t = i , функция подставляется на место переменной ССо функции и переменная Х0 функции 5 (л і.) не отождествлена ни с одной из свободных переменных функции -j( / Здесь возможны два варианта.
Алгоритмическая сложность задачи распознавания полноты
В этой главе описан метод построения алгоритмов для распознавания принадлежности функции Рс замкнутому классу сохранения предиката при этом предикат не обязательно будет фиксированным, то есть он может подаваться на вход алгоритма вместе с функцией j(x ) . Такая постановка задачи возникает, например, в случае необходимости построения алгоритмов распознавания принадлежности функций предикатно описуемым классам из некоторого растущего множества. Произведена оценка временной сложности алгоритмов, получаемых описанным методом. Функции будем задавать таблицами истинности, при этом сложность задания функции Ясс 1) есть N= It И , тогда как способ задания предикатов будет опреде ляться в каждом конкретном случае. Это может быть оправдано тем, что функции j [JX ) , вообще говоря, произвольны, предикат же обычно либо фиксирован, либо выбирается из некоторого узкого множества и поэтому сложность его задания может быть уменьшена по сравнению со сложностью табличного представления, выбором специального вида задания.
Для задачи распознавания принадлежности функции классу Ж ( R) , где К_ - /[-местный предикат, существует - 56 естественный алгоритм: достаточно просмотреть все выборки по t наборов длины % и проверить для каждой из них импликацию (I) . Сложность такого алгоритма Описанный в данной главе метод позволяет строить более быстрые алгоритмы.
Мы будем рассматривать алгебраические системы специального вида, а именно, через V ( А, А ) будем обозначать систему такую, что: I) имеется множество Л элементов 1, ,... с двумя бинарными операциями + и , такими, что А замкнуто относительно обеих операций, обе операции коммутативны и ас социативны, связаны законом дистрибутивности (й+Ь) С — CL t +DeC , и существует элемент 0 , такой, что 0L+O CL и (1 0=0 для любого CL А ; 2J в А выделено подмножество А , замкнутое относительно введённых выше операций, такое, что V Т А Будем считать, что все элементы множества А допускают кодировку, позволяющую их хранить и производить с ними определённые выше операции на вычислительном устройстве; длина кода элемента (X будет обозначаться через X (&)
Таким образом, временная сложность всего алгоритма не превосходит велечины, указанной в утверждении теоремы.
Если в п. 3 начать с разложения функций j. [X ) по переменной 3C k4j, » используя при построении функций J » [х ) коэффициенты характеристического выражения і (JR_) , а далее использовать коэффициенты характеристического выражения 1 V R) , то получим алгоритм, который также позволяет распознать принадлежность функции т(х J классу д (R) Оценка временной сложности последнего алгоритма может быть получена аналогично оценке временной сложности предыдущего алгоритма. Отсюда следует, что в п.4 первого алгоритма корректно решается вопрос о принадлежности функции j(5c / классу Эб(&) , Корректность второго алгоритма доказывается аналогично. Теорема- доказана.
Напомним, что при построении конкретных алгоритмов, мы используем модель вычислений с произвольным доступом к памяти, а целые числа представляем их двоичной записью.
Следствие 2.1. Если А - множество целых чисел, А множество натуральных чисел и предикат фиксирован, то верхние оценки временной сложности обоих алгоритмов совпадают и равны
При построении алгоритма для решения задачи о принадлежности функции jl / замыканию системы функций
Раосмотрвна задача распознавания принадлежности функции j ( / классам из растущего множества то есть предикат уже не является фиксированным. Переборный алгоритм решения этой задачи имеет временную сложность
На основе описанного выше метода был построен алгоритм решения этой задачи, имеющий временную сложность
Пример 3. Рассмотрим задачу распознавания принадлежности функции 5( / Pk классу сохранения некоторого произвольного двухместного предиката R(cci,JC4) . Переборный алгоритм в этом случае имеет временную сложность
В заключение данной главы заметим, что в следствиях 2.1 и 2.2 оценки сложности алгоритмов не зависят от сложности j характеристического выражения . Поэтому при постро ении алгоритмов распознавания принадлежности функции J [ее) фиксированным предикатно описуемым замкнутым классам при помощи следствия 2.1, или следствия 2.2 достаточно ограничиться отысканием характеристических выражений
Похожие диссертации на Алгоритмическая сложность решения некоторых задач в многозначных логиках
