Введение к работе
Актуальность темы
Диссертация посвящена одному из новых подходов к классификации подмножеств /V = {0>1*2»„.} множества всех целых неотрицательных чисел, который использует булевы функции и эффективную вычислимость. Первым, кто заинтересовался этим направлением, был Э- Пост [16]. Среди рекурсивно перечислимых множеств он определил классы рекурсивных, простых, креативных и мезоичных [11] множеств. Позже [10]» [12] класс мезоичных множеств был разбит на семейства псевдопростых и псевдокреативных множеств. Однако, как пишет в своей монографии X. Роджерс [8], 1Ьэто полезный каталог изученных к настоящему времени типов множеств, но с теоретической точки зрения» несколько произвольный". Другой подход к изучению произвольных подмножеств множества N заключается в их классификации по "сложности". Инструментом для такой классификации служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество А сводимо к множеству В, если существует алгоритм, который решал бы проблему вхождения элементов для множества А при условии^ что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных чисел из N множеству В. Наиболее пристальное внимание было уделено т -, табличной {ft -) и тьюринговой (Г -) сводимостям, введённых также Э. Постом. Среди рекурсивно персчислимых множеств от —полные (креативные [15]) являются наиболее "сложными", а рекурсивные, для которых существует эффективная процедура распознавания принадлежности к ним любого числа из ТУ, наиболее "простыми". Вопрос о существовании относительно Г -сводимости множеств, промежуточных по сложности, получили название проблемы Поста. Она была положительно решена независимо Р. Фрндбергом [13] и А. А, Мучником [7]* Что касается сводимостей, промежуточных между
т- и «-сводимостями, то основными оказались ещё пяты btti -оіраничснная tt -сводимость с нормой 1, с -конъюнктивная, d -дизъюнктивная, р-позитивная и /-линейная [I]* [9]. Важные
результаты о соотношениях между этими сводимостямн были получены А, а Дегтевым [2], [3], [4].
В работе [14] К. Джокуш ввбл понятое полурекурсивного множества, именно, подмножество А множества N называется полурекурсивным, если существует двуместная общерекурсивная функция (ОРФ) / такая, что
(v*X4rft/fc yh k j*} a W*)v xiy))=і ** f{x, yh л),
где #-хараісгеристическая функция множества Л, По аналогии А. Н. Деїтев определил понятие 0-комбинаторных [5] множеств, а именно, множество А называется //-комбинаторным, где р- произвольная «-местная булева функция, при условии /?(*,,.,, д;) = х, если существует «-местная общерекурсивная функция f % такая что
Оказалось, что число различных классов /?-комбинаторных множеств равно семи.
Если потребовать, чтобы ОРФ f была селекторной, т. е.
(Vx|,...,*w)(/(x| х„)є{*і хп})>
то придём к определению понятия р-селекторного [5] {р-комбинаторно-селекторного {р-КС)) множества. Выяснилось, что число различных классов /7-селеіггорііьіх множеств всего три: класс всех рекурсивных, класс всех
полурекурсивных и класс F* '— всех подмножеств /V,
Далее, если в определении /?-ком6инаторно*селекторного множества эквивалентность заменить на импликацию, то получим определение Д-имтикативно-селекторного (р-ИС) множества [6], множество А
называется /?-импликативио-селеісторньім, если существует л-местная селекторная ОРФ f такая, что
(Ухь...,ЖяХ^('І>...^(^))я=1^/(^".»'И)б4
Пусть F^m\ m > 1, семейство всех fim+\ -ИС множеств где
Aif+Ie & (xivxjh
Центральным результатом статьи [6] является следующая теорема: если /?-БФ такая, что /?(х,.„,х) = ха то семейство /7-ИС множеств совпадает с
одним из г ^ % m 2:1 или гч , причем имеют место строгие включения
Обобщением данных понятий послужили работы [17J и [18], rjig в определении в качестве f используется селекторная частично-рекурсивная функция (ЧРФ), т. е. такая, что
где f(x\»„.txff)
Именно, множество j4 с # называется слабо Р-хшгыикативно-селекторным (слабо fl-ИС)* где fi - w-местная буяева функция, если существует ^-местная частично-рекурсивная функция f такая, что:
Далее, множество А называется слабо fl-комбинаторно-селекторным множеством (слабо fi-КС)* если существует «-местная ЧРФ / такая, что
^Xv*l хлХ/^х11..-^хя)) = 1«*Дх1 хп)єА\
При этом в обоих определениях функцию / называют соответствующей множеству А.
Обозначим через K(fi) (/?(/?)) класс слабо /?-ИС (соответственно
/?-КС) множеств, считая размерностью K{fi) {R{fi)) число существенных
переменных булевой функции /?. Назовем функцию fi допустимой, если
р ?ь О, I и /?(0,„м0) = 0. Кроме того, будем рассматривать БФ ft с точносгью
до перестановки переменных- Рассмотрению именно этих классов множеств и посвящена настоящая диссертация.
Цель работы
При написании диссертационной работы были поставлены следующие цели: во-первых, описать классы К{0) и R{fi) для произвольных БФ /?; во-вторых, выяснить соотношения между этими классами по включению.
Основные методы исследования
В работе используются методы и средства, применяемые в теории алгоритмов, в частности, рекурсивно комбинаторные методы, метод приоритета и конструкции с использованием тернарных деревьев.
Научная новизна
Все основные результаты диссертации, выносимые на защиту, являются новыми. Они состоят в следующем:
полностью описаны все классы слабо /І -ИС множеств, размерность которых не превосходит трёх, как и монотонных слабо /У-ИС множеств размерности не выше четырёх, и выяснены соотношения межлу ними по включению (теоремы 1.1 J и 1.1.2)- В частности, классов монотонных слабо /?-ИС множеств оказалось бесконечно много (теорема ІЛ.З);
— полностью описаны все классы слабо /?-ИС множеств для линейных и самодвойственных (размерности не выше четырех) ЬФ /І и выяснены соотношения между ними по включению (теоремы 1.4,1 и 1,4*2);
полностью описаны все классы размерности 3 слабо fi-KC множеств как для монотонных, так и для немонотонных БФ р и выяснены соотношения между ними по включению- Этот результат также обобщен для случая БФ произвольной размерности (теоремы 2,2Л и 2,2.2).
Теоретическая н практическая ценность
Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в дальнейших исследованиях в теории алгоритмов, а также при чтении спецкурса.
Апробация результатов
Изложенные в диссертации результаты были представлены на международной конференции, посвященной 200-летию Казанского государственного университета (Казань, 2-9 июня 2004 года), а также на межрегиональных конференциях "Современные математические методы и информационные технологии в образовании" (Тюмень, 14-16 апреля 2005 года, 18 апреля 2007 года). Кроме того, полученные результаты регулярно докладывались на заседаниях кафедры алгебры и математической логики Тюменского государственного университета. По результатам работы автор выступал с докладом в Уральском государственном университете на семинаре "Алгебраические системы" (Екатеринбург, 8 февраля 2007 год).
Публикации
Основные результаты диссергации опубликованы в семи работах, список которых приведён в конце автореферата [17-23], Результаты первых трех из них получены в соавторстве с научным руководителем А. Н. Дйгтевым,
Стругоура диссертации
Текст диссертации состоит из оглавления, введения, двух глав, объединяющих 6 параграфов, заключения и списка литературы. Библиография включает 38 наименований. Общий объСм диссертации составляет 73 страницы.
