Конструктивизируемость структур и их степени неразрешимости тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 510.2

Фролов Андрей Николаевич

КОНСТРУКТИВИЗИРУЕМОСТЬ СТРУКТУР И ИХ СТЕПЕНИ НЕРАЗРЕШИМОСТИ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Казань — 2004

Работа выполнена на кафедре алгебры Казанского государственного университета

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

доктор физико-математических наук, профессор Арсланов Марат Мирзаевич

Официальные оппоненты:

доктор физико-математических наук, профессор Селиванов Виктор Львович

кандидат физико-математических наук, Подзоров Сергей Юрьевич

Ведущая организация:

Институт математики СО РАН им. Соболева

Защита диссертации состоится 23 декабря 2004 г. в 16 ч. 00 мин. на заседании Диссертационного Совета К 212.174 01 при Новосибирском государственном университете по адресу: 630090, Новосибирск-90, ул. Пирогова, 2.

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

Автореферат разослан "22" ноября 2004 г.

Ученый секретарь Диссертационного Совета К 212.174.01, кандидат физико-математических наук

А.Д. Больбот

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

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

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

Исследования в этой области начались в 1960-х годах Л. Фейнером и продолжены в работах Дж. Реммела. С.С. Гончарова, Дж. Найт, К. Эша и других. Наибольший интерес у работающих в данной области отечественных и зарубежных математиков вызывают исследования алгоритмических свойств таких классических алгебраических структур, как группы, кольца, линейные порядки, булевы алгебры и другие.

Несмотря на значительное количество серьезных результатов, полученных различными учеными по данной тематики, большое количество проблем до сих пор остаются открытыми, поэтому теория конструктивизируемых структур требует дальнейшей разработки. Следовательно, рассмотрение таких структур, как булевы алгебры, алгебры Ершова и линейные порядки, является важным элементом построения этой теории и представляет определенный интерес.

Цель работы. Основными целями диссертации является решение открытого вопроса, поставленного Р. Миллером1, описание конструктивизи-руемых n-низких "сильно похожих на if и квазидискретных (в частности, дискретных) линейных порядков и алгебр Ершова, а также исследование теоретико-множественной структуры класса вычислимых множеств.

Методы исследования. При доказательстве теорем диссертации использовались методы конечных расширений, приоритета с конечными нарушениями (метод О'-приоритета), приоритета с бесконечными нарушениями (метод 0"-приоритета). Например, теоремы 4.1.4 и 4.6.1 доказывались методом конечных расширений, теорема 3.1.7 — методом приоритета с конечными

'R. МШег, The spectrum of a linear ordering // The Journal of Symbolic Logic, 66,

2001, 470 486. 1 ^ЪМЩМИИИИШ!

|3 мшит J

нарушениями, а теорема 2.3 3 — методом приоритета с бесконечными нарушениями.

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

Теоретическая и практическая значимость. Диссертационная работа носит теоретический характер. Она является продолжением, развития теории конструктивизируемых структур. Методы исследования могут быть применены для изучения ri-низких алгебр Ершова и линейных порядков различных порядковых типов

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

1. "Logic Colloquium" (2001 г. Австрия, 2002 г. Германия, 2003 г. Финляндия, 2004 г. Италия),

. 2. "Колмогоров и современная математика" (Москва, апрель 2003 г.).

3."Мальцевские чтения" (Новосибирск, 2003 г.),

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

Публикации. Четырнадцать работ [1] — {14], опубликованных автором по теме диссертации, полностью отражают ее содержание. Список статей приведен в конце автореферата.

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

» щ «г* ff

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

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

В первой главе исследованы спектры счетных линейных порядков, различных порядковых типов. Основным результатом этой главы является теорема 1.1.10, она отвечает на открытый вопрос, сформулированный Р. Миллером2.

Теорема 1.1.10 Для любого Hi О) существует такой линейный порядок £„, что Spec*°[Ln) = Д, - L„.

Также в этой главе были доказаны следующие результаты:

Теорема 1.3.3 Любой сильно похожий на п линейный порядок низкой степени изоморфен вычислимому порядку

Следствие 1.4.9 Каждый кваэидискретный линейный порядок 2-низкой степени имеет вычислимую копию.

В работе также показано, что утверждение теоремы 1.3.3 не верно для 2-низких порядков, а утверждение следствия 1.4.9 — для 3-низких порядков.

Основным результатом второй главы является следующий результат (следствие 2.2.16)

Каждая 8-низкая алгебра Ершова изоморфна вычислимой алгебре.

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

2R. Miller, The tpectrum of a hnear ordering // The Journal of Symbolic Logic, 66, 2001, 470 - 486.

Теорема Пусть V — класс полиномиально вычислимых множеств или класс примитивно рекурсивных множеств, тогда для любых таких множеств А,В Е 72, что А Сю В существует

1) (Следствие 3.1.5) V-бииммунное в А Соо В множество;

2) (Следствие 3.1.8) строго V-иммунное над А множество;

S) (Следствие 3.1.8) строго V-коиммунное под В множество;

4) (Теорема 3.1.7) V-пределънос множество X A Coo X Соо В.

Теорема 3.1.10 Если V - класс полиномиально вычислимых множеств или класс примитивно рекурсивных множеств, то для любого вычислимого множества А существуют такие V-предельные множества D\, Dj, D3 и

Dt, что A = (DlU Dt) П (Da U Dt).

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

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

Автор выражает глубокую признательность своему научному руководителю профессору Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе.

Литература

[1] А.Н. Фролов Теоретико-множественная структура вычислимых множеств Ц Известии вузов. Математика, 2003, 10 (497), 70 - 76.

[2] А.Н. Фролов Теоретико-множественные сводимости по решетке множеств // Известии вузов. Математика, принята к печати.

[3] А.Н. Фролов SET-1-сводимость на классе вычислимых множеств // Известии вузов. Математика, принята к печати.

[4] А.Н. Фролов копии линейный порядков // Алгебра и логика, в печати.

[5] А.Н. Фролов Вычислимые алгебры Ершова // Казань: Казанское математическое общество, 2004, Препринт 04/2.

[6] A.N. Frolov On the class of recursive sets // Proceedings of "Logic Colloqumm'200 г, Vienna (Austria), August 2001, p. 144.

[7] A.N. Frolov Set-theoretical properties of classes of computable sets Ц Proceedings of "Logic Colloquium'2002", Munster (Germany), August 2002, p. 33.

[8] А.Н. Фролов Теоретико-множественная структура вычислимых множеств // Труды XXIV конференции молодых ученых, апрель 2002, МГУ, Т.И , 179 - 182.

[9] А.Н. Фролов Структура вычислимых множеств // тезисы лучших докладов итоговой научной студенческой конференции 2001 года, Казанский государственный университет, 2002, 41 - 42.

[10] А.Н. Фролов Алгебры Ершова, имеющие вычислимую копию // тезисы конференции "Колмогоров и современная математика", апрель 2003, 709 -710.

[11] A.N. Frolov Computable copies of Boolean and Ershov algebras /f Proceedings of "Logic Colloquium 2003", Helsinki (Finland), August 2003.

[12] А.Н. Фролов Алгебры рекурсивных множеств // тезисы лучших докладов итоговой научной студенческой конференции 2002 года, Казанский государственный университет, 2003, 130 - 131.

[13] A.N. Frolov Computable copies of distributive lattices with relative complements and linear ordenngs // Proceedings of "Logic Colbquium'2004", Turin (Italy), July 2004, p. 78.

[14] А.Н. Фролов Д^-спсктры линейных порядков // тезисы конференции "Алгебра и анализ-2004", Казань, июнь 2004, с. 71.

Отпечатано с готового оригинал-макета в типографии Издательского центра Казанского государственного университета им.В. И.Ульянова-Ленина Тираж 100 экз. Заказ 11/44

420008, ул. Университетская, 17 тел.: 31-53-59,92-65-60

•25387

Введение

1 Д°-спектры линейных порядков

1.1 -спектр.

1.2 Линейные порядки, сильно похожие на

1.3 Квазидискретные линейные порядки.

2 Вычислимые алгебры Ершова

2.1 2-низкие алгебры Ершова.

2.2 3-низкие алгебры Ершова.

3 Класс вычислимых множеств

3.1 Теоретико-множественная структура.

3.2 Теоретико-множественные сводимости.

3.3 SET-1-сводимость на классе вычислимых множеств.

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

Исследования в этой области были начаты JI. Фейнером в конце 1960-х и продолжены в работах Дж. Реммела, С.С. Гончарова, Дж. Найт, К. Эша и других. В частности, было показано, что существуют вычислимо перечислимые булева алгебра и линейный порядок, не имеющие вычислимые изоморфные копии (см. [1] и [2]), другими словами, являющиеся неконструк-тивизируемыми.

В последние года активно изучаются такие вопросы, как описание спектра счетных алгебраических структур. Например, Т. Сламан (см. [3]) и С. Вей-нер (см. [4]) независимо друг от друга построили такую счетную структуру А, что Spec(A) — D — {0}, где D — класс всех тьюринговых степеней. Р. Миллер в [5] доказал, что существует такой линейный порядок L, что Spec(L) П = Д° — {0}. С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого п € ш такую структуру An, что Spec(An) = D — Ln, где Ln — класс всех п-низких степеней.

В этой работе мы докажем, что для любого п 6 ш существует такой линейный порядок Сп, что Spec(£n) П = А° — L„.

В [7] Р. Доуни и М. Мозес показали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Мы обобщим этот результат, доказав, что каждый 2-низкий квазидискретный (и, следовательно, дискретный) линейный порядок изоморфен вычислимому порядку. Причем, покажем, что для 3-низких квазидискретных порядков этот результат не верен.

Также Р. Доуни спросил, какие еще существуют свойства линейных порядков Р, что для любого низкого линейного порядка L из P(L) следует существование вычислимой копии. В этом направлении мы докажем, что каждый низкий линейный порядок, "сильно похожий" на ?/, изоморфен вычислимому порядку (причем для 2-низких это не верно).

Отечественными и зарубежными учеными активно исследуется также вопрос о та-низких булевых алгебрах и алгебрах Ершова. В [1] JI. Фейнер построил вычислимо перечислимую булеву алгебру, не изоморфную никакой вычислимой алгебре. Построенная им булева алгебра не изоморфна никакой n-низкой алгебре, ни для какого натурального п. Естественно возникает вопрос: каждая ли та-низкая (для любого п € ш) булева алгебра имеет вычислимую копию? Постановку этого вопроса можно найти, например, в [8].

В общем случае ответ на этот вопрос пока неизвестен, известны частичные ответы. В [9] Р. Доуни и К. Джокуш доказали, что каждая низкая булева алгебра изоморфна вычислимой алгебре. В [8] Дж. Найт и М. Стоб доказали, что любая 4-низкая булева алгебра имеет вычислимую копию. В этой работе мы покажем, что каждая 3-низкая алгебра Ершова изоморфна вычислимой алгебре.

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

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

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

При доказательстве теорем диссертации использовались методы конечных расширений, приоритета с конечными нарушениями (метод 0'-приоритета), приоритета с бесконечными нарушениями (метод 0"-приоритета). Например, теоремы 3.1.5, 3.3.11 доказывались методом конечных расширений, теорема 2.1.2 — методом приоритета с конечными нарушениями, а теорема 1.2.3 — методом приоритета с бесконечными нарушениями.

Содержание диссертации представлено в собственных публикациях автора [11] — [24]. Результаты, изложенные в данной работе, докладывались на международных конференциях "Logic Colloquium'2001" (Вена, Австрия, август 2001 г.), "Logic Colloquium'2002" (Мюнстер, Германия, август 2002 г.), "Колмогоров и современная математика" (Москва, апрель 2003 г.), "Logic Colloquium'2003" (Хельсинки, Финляндия, август 2003 г.), "Мальцевские чтения" (Новосибирск, 2003 г.), "Logic Colloquium'2004" (Турин, Италия, июль 2004 г.), а также на научных семинарах; по математической логике в Казанском государственном университете.

Автор выражает глубокую признательность своему научному руководителю профессору Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе.

В изложении теории вычислимости (теории алгоритмов) мы следуем в основном [10], в изложении теории счетных булевых алгебр, алгебр Ершова и линейных порядков — [25].

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

Обозначения и терминология.

Теория вычислимости. Через ш обозначается множество всех натуральных чисел с 0.

Функция (ж, у) = (ж2 + 2ху 4- у2 + Зж + у)/2 — стандартная вычислимая биекция из и> • ш в ш.

Теоретико-множественную разность множеств X С ш и Y С ш будем обозначать через X—Y] дополнение множества X С. ш — через X =dfn ш—Х.

Мы будем иногда отождествлять множество А Cw с его характеристической функцией

Г 1, если ж 6 А, Хл(х) = < 0, в противном случае, так что запись А(х) — 1 означает, что х 6 А, а А{ж) = 0 эквивалентно х £ А.

Запись X =* Y означает, что симметрическая разность (X — У)и(У — X) конечна.

Будем писать А С* В, если А— В конечно. Пишем А Соо В, если А С.* В и В%* А.

Тьюринговые степени будем обозначать жирными строчными латинскими буквами а, b, ., тьюринговую степень множества А обозначаем через deg(A).

Если / — некоторая функция, то dom(f) — область ее определения, rang(f) — область ее значений, graph(f) — график функции /: graph(f) = {(ж,у) | у = /(ж)}.

Если последовательность функций /я : о> —и> поточечно сходится к функции /, то будем писать / = lims f3.

Функция называется примитивно рекурсивной, если она принадлежит наименьшему классу, содержащему функции 0(х) = 0, s(x) =dfn ж -f- 1, /£(ж1,., жп) —dfn хт и замкнутому относительно суперпозиции и примитивной рекурсии.

Функция называется вычислимой (частично вычислимой), если существует машина Тьюринга, вычисляющая эту функцию.

Функция называется полиномиально вычислимой, если она вычислима на машине Тьюринга за количество шагов, ограниченное некоторым наперед заданным полиномом.

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

Множество называется вычислимо перечислимым, если оно является областью определения некоторой частично вычислимой функции. ф£ — одноместная частично вычислимая функция, вычислимая на машине Тьюринга с оракулом А с гёделевым номером еби.

Для каждого е полагаем W^ —dfn <1от(ф£).

Оператором скачка множества А является А' — {е | е £ Wj1}. По индукции можем определить n-ый скачек множества A: = (А^)'.

Для № G w множество А <т 0' называется ?г-низким (или та-высоким), если <т (или 0(n+1) <т А'"', соответственно). Тьюринговая степень а называется га-низкой или та-высокой, если некоторое множество А £ а является п-низким или п-высоким, соответственно. 1-низкое (1-высокое) множество или степень называется просто низким (высоким, соответственно).

Булевы алгебры, алгебры Ершова, линейные порядки и их тью-ринговы степени.

Алгеброй Ершова называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший элемент. Булевой алгеброй называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший и наибольшие элементы.

Идеалом Фреше булевой алгебры V называется идеал Т{ТУ) = {а <Е Т> \ Вах,., ап, где а; — атом или нуль, 1 < i < га}.

Под понятием решетки множеств понимается класс множеств V С V(u) — {А | А С о;}, замкнутый относительно операций объединения и пересечения (то есть A U В, Л П В £ Р для любых множеств А, В G Т>).

Решеткой множеств с наименьшим (с наибольшим) элементом назовем решетку множеств Т>, если 0 € Т> (или ш G Т>, соответственно).

Под алгеброй множеств понимается решетка множеств с наименьшим и наибольшим элементами, замкнутая относительно операции теоретико-множественной разности (то есть А — В € Z? для любых А, В € Т>).

Автоморфизмом алгебры множеств А называется такая биекция <р : А —> Л, что для любых А,В е A <p(A)U<p(B) = <p(A(jB) и ip(A)C\ip(B) = ц>(АГ\В).

Степень структуры В, обозначается deg(#), — это тьюринговая степень ее атомной диаграммы, закодированной геделевскои нумерацией как подмножество ш. Если сигнатура структуры В конечна, то тьюринговой степенью В является deg(0) = deg(|B|) V (V?=0 deg(/;)) V (V£0 deg(Pi)), где \B\ — основное множество, {fi}i<n и {Pi}t<m — все функции и предикаты сигнатуры структуры В, соответственно.

Мы рассматриваем только счетные структуры, основным множеством которых является и).

Спектром структуры Л называется класс Spec(A) = {deg(B) | В = Л}.

Если С — некоторый класс степеней, то С-спектром называется класс Spec0(Л) = С nSpec(A).

Мы будем рассматривать только -спектры счетных линейных порядков, то есть С = Ag — класс всех таких степеней а, что а <т О', где О — степень вычислимых множеств.

Мы будем говорить, что структура Л вычислима (n-низкой степени или п-высокой степени), если его степень deg(A) вычислима (n-низкая или п-высокая, соответственно).

1. L.J. Feiner Hierarchies of Boolean algebras / / The Journal of Symbolic Logic, 35, 1970, 365 - 373.

2. L.J. Feiner Orderings and Boolean algebras not isomorphic to recursive one II PhD. thesis, MIT, 1967.

3. T. Slaman, Relative to any nonrecursive set // Proceedings of the American Mathematical Society, 126, 1998, 2117 2122.

4. S. Wehner, Enumeration, countable structure and Turing degrees // Proceedings of the American Mathematical Society, 126, 1998, 2131 2139.

5. R. Miller, The spectrum of a linear ordering // The Journal of Symbolic Logic, 66, 2001, 470 486.

6. S.S. Goncharov, V.S. Harizanov, J.F. Knight, C. McCoy, R. Miller, R. Solomon, Enumerations in computable structure theory //в печати.

7. R.G. Downey and M.F. Moses, On choice sets and strongly nontrivial self-embeddings of recursive linear orderings // Z. Math. Logik Grunall. Math., 35, 1989, 237 246.

8. J.F. Knight and M. Stob Computable Boolean algebras, The Journal of Symbolic Logic, 65, 2000, No 4, 1605 1623.

9. R.G. Downey and C.G. Jockusch, Every low Boolean algebra is isomorphic to a recursive one / / Proceedings of the American Mathematical Society, 122, 1994, No 3, 871 880.

10. R.I. Soaxe Recursively enumerable sets and degrees, Heidelberg: Springer-Verlag, 1987 (см. русский перевод: Coap P. И. Вычислимо перечислимые множества и степени Казань: Казанское мат. общество, 2000, 576 с.)

11. А.Н. Фролов Теоретико-множественная структура вычислимых множеств // Известии вузов. Математика, 2003, 10 (497), 70 76.

12. А.Н. Фролов Теоретико-множественные сводимости по решетке множеств // Известии вузов. Математика, принята к печати.

13. А.Н. Фролов SET-1-сводимость на классе вычислимых множеств // Известии вузов. Математика, принята к печати.

14. А.Н. Фролов копии линейных порядков // Алгебра и логика, в печати.

15. А.Н. Фролов Вычислимые алгебры Ершова // Казань: Казанское математическое общество, 2004, Препринт 04/2.

16. A.N. Frolov On the class of recursive sets // Proceedings of "Logic Colloquium'2001", Vienna (Austria), August 2001, p. 144.

17. A.N. Frolov Set-theoretical properties of classes of computable sets // Proceedings of "Logic Colloquium'2002", Munster (Germany), August 2002, p. 33.

18. А.Н. Фролов Теоретико-множественная структура вычислимых множеств // Труды XXIV конференции молодых ученых, апрель 2002, МГУ, т.II , 179 182.

19. А.Н. Фролов Структура вычислимых множеств // тезисы лучших докладов итоговой научной студенческой конференции 2001 года, Казанский государственный университет, 2002, 41 42.

20. А.Н. Фролов Алгебры Ершова, имеющие вычислимую копию // тезисы конференции "Колмогоров и современная математика", апрель 2003, 709 710.

21. A.N. Frolov Computable copies of Boolean and Ershov algebras // Proceedings of "Logic Colloquium'2003", Helsinki (Finland), August 2003.

22. A.H. Фролов Алгебры рекурсивных множеств // тезисы лучших докладов итоговой научной студенческой конференции 2002 года, Казанский государственный университет, 2003, 130 131.

23. A.N. Frolov Computable copies of distributive lattices with relative complements and linear orderings // Proceedings of "Logic Colloquium'2004", Turin (Italy), July 2004, p. 78.

24. A.H. Фролов Дд-спектры линейных порядков // тезисы конференции "Алгебра и анализ-2004", Казань, июнь 2004, с. 71.

25. С.С. Гончаров Счетные булевы алгебры и разрешимость. Новосибирск: Научная книга, 1996.-364 с.

26. R.G. Downey, On presentations of algebraic structures, in Complexity, Logic, and Recursion Theory, ed. A. Sorbi (New York: Dekker, 1997), 157 205.

27. R.G. Downey and J.F. Knight, Orderings with a-th jump degree // Proceedings of the American Mathematical Society, 14, 1992, 545 552.

28. R. Watnik, A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings // The Journal of Symbolic Logic, 49, 1984, 563 569.

29. K. Ambos-Spies Honest polinomial time reducibilities and the P=NP problem // J. Comput. System Sci., 1989, vol. 39, pp. 250 281.

30. А.И. Мальцев Алгоритмы и рекурсивные функции Москва: "Наука", 1986, 367 с.