Теория алгоритмов зародилась в тридцатых — сороковых годах прошлого столетия благодаря работам А. Тьюринга [30] и С. Клини [22]. В этих работах была доказана эквивалентность различных уточнений понятия вычислимой функции и обоснован известный тезис Чёрча. Другой основополагающей работой в этом направлении принято считать статью Э. Поста [26], опубликованную в 1944 году. В ней обращено внимание на те подмножества N = {0,1,2,.}, элементы которых можно эффективно перечислять, такие подмножества образуют класс рекурсивно-перечислимых множеств (РПМ). Наиболее «простыми» из них являются так называемые рекурсивные множества, для которых имеются алгоритмы, позволяющие правильно отвечать на вопросы о принадлежности к ним любых чисел из N. В этой же статье Э. Пост привёл некоторые примеры нерекурсивных рекурсивно-перечислимых множеств, в частности креативных и простых. Существуют и другие, которые были названы Деккером [15] мезоичными. Классификация РПМ была предпринята Деккером и Майхиллом [16] и Успенским [13], которые разбили класс мезоичных множеств на псевдопростые и псевдокреативные множества. В результате дальнейшего разбиения были получены другие классы. Это широкий список изученных к настоящему времени типов множеств, но с теоретической точки зрения, несколько произвольный.
Один из подходов к изучению свойств РПМ заключается в рассмотрении решётки которую образует семейство всех РПМ вместе с операциями пересечения и объединения множеств. Оказалось, что в решётке? определены классы рекурсивных, простых, рекурсивно неотделимых и других множеств. Д. Мартин доказал, что класс гиперпростых множеств не определим в этой решётке [27]. В 1983 году была установлена неразрешимость элементарной теории? [18], [19].
Существенный вклад в изучение решётки? внесли Р. Фридбергер [17], построивший максимальное множество, и А. Лахлан [25], описавший класс, так называемых гипергиперпростых множеств. Эти множества являются определимыми в решётке Неожиданным оказался результат Харрингтона.
29], который доказал определимость в t креативных множеств. Последние успехи в данном направлении отражены в книге Р. Соара [12], который получил важные результаты об автоморфизмах? [28].
Другой подход к изучению РПМ и произвольных подмножеств множества N заключается в попытке их классификации по «сложности». Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество, А сводимо к множеству В, если существует алгоритм, который решал бы проблему вхождения элементов для множества, А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В. В этом случае, А оказывается «проще устроено», чем А, или (в определённом смысле) А рекурсивно относительно В. Такая сводимость в наиболее общем виде называется Тыоринговой (Т-) сводимостью.
Наряду с Т — сводимостью уже в 1944 году Э. Пост [26] ввел некоторые специальные виды сводимостей, такие как m — сводимость, табличная (// -) и ограниченная табличная (btt -) сводимости. Именно, множество, А тсводимо к множеству В {А <т В), если существует всюду определенная на N вычислимая функция / такая, что хеЛ<=> f (x)eB для всех xeN. Множество A ttсводимо к В (А <п В), если существует алгоритм, который для каждого xeN дает набор чиселп (х)) и булеву функцию.
0хуи->Уп (х)) такие> что х)[х е, А о х[*п (х)]}= l)> где z (0 = Ь если ' и z (0 = ®> если частности, если п (х) для всех д: не больше некоторого фиксированного числа, то говорят, что, А btt — сводимо к В. Сводимости, промежуточные по своей силе между т — и tt — сводимостью, были названы сводимостями табличного типа.
Как выяснилось, на множестве всех собственных подмножеств N существуют в точности семь различных основных сводимостей, а именно: m,, с, d, pj, tt [1], [11], гдеограниченная //-сводимость с нормой 1, с — конъюнктивная, й? — дизъюнктивная, р-позитивная и /-линейная сводимости. Каждая сводимость г, если положить, А =г В <=> А <г В лВ <г А, разбивает множество подмножеств N на классы эквивалентности, называемые г — степенями. Если г — степень содержит РПМ, то её называют рекурсивно перечислимой г — степенью. Важные результаты о строении верхних полурешёток РП г — степеней [3], а так же о соотношении между различными сводимостями табличного типа [5], [6], [7] были получены А. Н. Дегтевым. Кроме того, решена проблема соотношения между классами г-полных множеств [4] и установлено, что элементарные теории полурешёток Ltt, Ц, Lp, Lj, Lc, Lm и попарно различны [2].
Ещё одна классификация подмножеств множества N была предложена А. Н. Дёгтевым. В работе [20] К. Джокуш ввёл понятие полурекурсивного множества, именно, подмножество, А множества N называется полурекурсивным, если существует двуместная общерекурсивная функция (ОРФ) / такая, что.
Vx)(Vy)(/(x, у) е {х, л (*(*) v Х (у)) =1<* f (x, у) е А), где х — характеристическая функция множества А. По аналогии А. Н. Дёгтев определил понятие /?-комбинаторных [8] множеств, а именно, множество, А называетсякомбинаторным, где /?-произвольная «-местная булева функция (БФ), если существует и-местная общерекурсивная функция (ОРФ) / такая что.
Щ,., х"№{х (х11., х (х")) = 1 <=> f{xh., xn) e А), Оказалось, что классы-комбинаторных множеств тесно связаны с основными сводимостями табличного типа.
Если потребовать, чтобы ОРФ/была селекторной, т. е. fxh., xnXf (x,., xn) e{xh., xn}), то придём к определению понятия /3-селекторного [8] (/?-комбинаторно-селекторного (у3-КС)) множества. Выяснилось, что семейство /?-селекторных множеств совпадает либо с семейством всех рекурсивных, либо с семейством всех полурекурсивных множеств, либо с семейством всех подмножеств N.
Далее, если в определении (3-комбинаторно-селекторного множества эквивалентность заменить на импликацию, то получим определение /?-импликативно-селекторного (/? -ИС) множества [10], множество, А называется /?-импликативно-селекторным, если существует «-местная селекторная ОРФ/такая, что.
Доказано, что если рБФ, такая, что р (х, х,., х) = х, то семейство /?-ИС множеств совпадает с одним из F^m т> 1, или с причём имеют место строгие включения.
F (1)cF (2)c.cFWc.cFW) здесь, F^ - семейство всех d*m+ -ИС множеств, где d*m+1= & {xiVXj).
1 </'< j.
Обобщением данных понятий послужили работы [32] и [33], где в определении в качестве / используется селекторная частично-рекурсивная функция (ЧРФ), т. е. такая, что где f{x,., xn) i означает, что значение f{xi,., xn) определено.
Именно, множество AqN называется слабо [3-импликативно-селекторным (слабо /3-ИС), где (3 — п-местная булева функция, если существует «-местная частично-рекурсивная функция/такая, что:
Vxjхп Шх{ц),-., zfan)):=1 Ах>•••>хп)еАп{х v. хп}).
При этом функцию/называют соответствующей множеству А.
Далее, множество, А называется слабо (3-комбинаторно-селекторным множеством (слабо /3-КС), если существует я-местная ЧРФ/такая, что х&bdquo-)(/{х{,., х&bdquo-) f{x,., хп) е foхп}) — 6)(Vx],., х&bdquoMz (x 1),., %(хп)) = Ю f{x,., хп) е А), где х — характеристическая функция множества А. Функция /соответствует множеству А.
Обозначим через К{(3) (R{0)) класс слабо /3-ИС (соответственно (3-КС) множеств, считая размерностью К{(3) {R{0)) число существенных переменных булевой функции (3. Назовём функцию [3 допустимой, если /7*0,1 и /?(0,., 0) = 0.
Данная работа посвящена рассмотрению именно этих классов множеств, при изучении которых были поставлены следующие задачи: во-первых, описать всевозможные классы К ((3) и R{0) для произвольных БФ /3- во-вторых, выяснить соотношения между этими классами по включению. Работа состоит из введения, двух глав, объединяющих 6 параграфов, заключения и списка использованной литературы, насчитывающего 38 наименований.
В главе 1 изучаются слабо /?-импликативно селекторные множества, где Р-допустимая БФ. В § 1.1, с использованием определённой техники, выписаны все допустимые БФ, зависящие от двух и трёх переменных (с точностью до их перестановок). В § 1.2 описаны с точностью до включения все классы К (р) слабо P-WC множеств для допустимых БФ, размерность которых не превосходит трёх. Центральным результатом данного параграфа является.
ТЕОРЕМА 1.2.1. [33]. Каэ/сдый класс К{0) слабо импликативно-селекторньгх множеств, размерность которого не превосходит трёх, совпадает с одним из классов К0 = К (х v у), К = К{ху v xz v yz), Kj = к{ху v ху), К2 = к (хуг v xyz v xyzj, К4 = К{х), причём Kg с К2 с К^ а К4 и Kq с К с К^ и все включения строгие.
Полученный результат можно изобразить в виде диаграммы включений классов К{0):
§ 1.3 посвящен изучению классов слабо /?-ИС множеств монотонных БФ, размерность которых не выше четырёх. Доказана следующая.
ТЕОРЕМА 1.3.2. [36]. Если /? -монотонная булева функция, и К{0) имеет размерность не выше четырёх, то К (/3) совпадает с одним из классов: К (х v у), К (ху v xz v yz), К (и (ху vxzv yz) v xyz), К (х), и к (х v у) с К{ху V xz v yz) С к{и{ху v xz v yz) v xyz) С к (х), причём все включения строгие.
Кроме того, доказывается, что классов монотонных слабо /?-ИС множеств существует бесконечно много (теорема 1.3.1).
Наконец, в § 1.4 получены результаты для произвольных линейных и самодвойственных БФ, размерность которых не выше четырёх. Они отражены в следующих двух теоремах.
ТЕОРЕМА. 1.4.1. [34]. Если /? — допустимая линейная булева функция, то класс К{0) совпадает с одним из классов: К{х v у), к[ху v ху), К (х), и.
К (х v у) с К.{ху v ху) с причем все включения строгие.
ТЕОРЕМА. 1.4.2. [34] Класс самодвойственных слабо импликатнвно селекторных множеств размерности не выше четырёх совпадает с одним из классов: К{х v у), К (ху vxzv yz), К (х и.
К (х v у) с к (ху v xzv yz) с К{х), причем включения везде строгие.
В главе 2 изучаются слабо /3-КС множества. В § 2.1 рассматриваются классы, порождённые монотонными БФ. Вначале получен ответ для тех БФ, размерность которых не превышает трёх. Затем этот результат был обобщён для БФ произвольной размерности и доказана.
ТЕОРЕМА 2.1.1. [37]. Если (3 -монотонная булева функция, то R{P) содержится в одном из следующих классов:
R (x v у), R (xy v xz v yz), R (xy), R (x), и.
R (x v у) с R (xy v xzv yz) с R (xy) с причём включения везде строгие.
В случае немонотонных БФ (§ 2.2) оказалось, что если а-немонотонная БФ, то всякое слабо «-КС множество имеет рекурсивно перечислимое дополнение. После рассмотрения всевозможных случаев БФ получен следующий результат:
ТЕОРЕМА 2.2.1. [37]. Если Р — немонотонная булева функция, то класс R{ft) совпадает или с классом всех рекурсивных множеств, или с классом всех полурекурсивных множеств с рекурсивно-перечислимыми дополнениями или с классом всех множеств, имеющих рекурсивно-перечислимые дополнения.
ЗАКЛЮЧЕНИЕ
.
Таким образом, основными результатами данной работы являются:
1. Найдены все, с точностью до перестановки переменных, допустимые БФ, зависящие от трёх переменных.
2. Полностью описаны все классы слабо /3 -ИС множеств, размерность которых не превосходит трёх, как и монотонных слабо (3-ИС множеств размерности не выше четырёх, и выяснены соотношения между ними по включению (теоремы 1.1.1 и 1.1.2). В частности, классов монотонных слабо /?-ИС множеств оказалось бесконечно много (теорема 1.1.3).
3. Полностью описаны все классы слабо /?-ИС множеств для линейных и самодвойственных (размерности не выше четырёх) БФ /? и выяснены соотношения между ними по включению (теоремы 1.4.1 и 1.4.2).
4. Полностью описаны все классы размерности 3 слабо (3-КС множеств как для монотонных, так и для немонотонных БФ /3 и выяснены соотношения между ними по включению. Этот результат также обобщён для случая БФ произвольной размерности (теоремы 2.2.1 и 2.2.2).
