Алгоритмические сводимости счетных алгебраических систем

Оглавление
' і
1 Массовые проблемы представимости алгебраических
систем 17
1.1 Массовые проблемы и решетка Медведева ................ 17
1.2 Проблемы представимости алгебраических систем и их
спектры степеней...................................... 22
1.3 Сводимость по перечислимости.......................... 26
1.4 Е-оводтшости алгебраических систем.................... 28
1.5 Обозначения и терминология............................ 30
2 Тотальные степени по перечислимости 31
2.1 Тотальные е-степени и операция скачка в е-степепях . . 31
2.2 Тотальные о-степепи и простейшие принципы теории
вычислимости.......................................... 49
2.3 Тотальные е-степони и относительная квазимимальность 54
2.4 Свойства разложимости тотальных е-степеней............ 72
3 Массовые проблемы перечислимости семейств 92
3.1 Предварительные сведения.............................. 92
3.2 Новые спектры степеней................................ 93
3.3 Операции на нумерациях и спектры......................106
3.4 Вычислимые нумерации Е^-множеств......................124
4 Ограничения на спектры степеней алгебраических систем 132
1
4.1 Нерешеточность полурешеток и ..........................134
4.2 Равномерность сводимости к алгебраическим системам
и тотальные е-степени.................................142
4.3 Случай линейных порядков...............................148
4.4 Спектры степеней систем произвольной сигнатуры . . . 154
4.5 Построение степени Ь < О" для которой совокупность
{х | х Ь} не является спектром .......................157
5 Частичные проблемы представимости алгебраических систем 170
5.1 Спектры е-стеиеней семейств подмножеств множества натуральных чисел..........................................171
5.2 Относительная Е-оиределимость семейств в допустимых множествах.............................................182
5.3 Соотношения между сводимостями алгебраических систем ......................................................196
2
Введение
В диссертации исследуются алгебраические системы с точки зрения их алгоритмической сложности с помощью двух взаимосвязанных подходов. Первый подход заключается в расширении сводимости по перечислимости на алгебраические системы, а второй основывается на понятие спектра степеней алгебраической системы. Оба подхода могут быть успешно формализованы на языке сводимостей массовых проблем, введенных Медведевым [5] в 1955 году.
Сводимость но перечислимости (е-сводимость) была введена Роджерсом [32] как расширение тьюринговой сводимости всюду определенных (тотальных) функций на частичные функции, определенные лишь на подмножествах натуральных чисел. Степенями по перечислимости (е-степенями) были названы классы эквиваленосги относительно отношения взаимо-е-сводимости двух множеств друг к другу. Роджерсом было введено понятие тотальной е-степепи — это в точности образы тыоринговых степеней, относительно канонического вложения верхней полу решетки тыоринговых степеней в полурештку степеней но перечислимости. Роджерсом [32] была поставлена фундаментальная проблема инвариантности класса тотальных е-степеией в полурештке степеней по перечислимости. Эта проблема до сих пор остается нерешенной.
Другое фундаментальное понятие, связанное со сводимостью по перечислимостью, операция скачка, было введено Розинасом [8] и Купером [15]. Данная операция также является обобщением (расшире-
3
ниєм) операции скачка в тьюринговых степенях. Поскольку областью значений операции скачка являются только тотальные е-степени, с проблемой инвариантности класса тотальных е-степеней тесно связана проблема инвариантности оператора скачка в полурешетке степеней по перечислимости. Купером [16] и Сорби [40] были поставлены проблемы определимости класса тотальных е-степеней и операции скачка на языке первого порядка упорядочения е-степеней. В диссертации получено частичное решение первой проблемы и полное решение второй.
Понятия степени и спектра степеней алгебраической системы было введено Рихтер |31] в 1981 году. Цель введения степени алгебраической системы заключалась в попытке классифицировать сложность неконструктивизируемых алгебраических систем с помощью тыорин-говых степеней, структура которых была к тому времени достаточно хорошо изучена. Однако самой же Рихтер [31] было обнаружено, что не каждый спектр степеней алгебраической системы имеет наименьший элемент, то еегь не каждая алгебраическая система имеет степень. Более того, остается до сих пор не решенной задача описания возможных спектров степеней алгебраических систем. В этом направлении работали и работают много российских и зарубежных исследователей (см. например [17], [19],[21],[22],[25], [37],[41],[42]).
В настоящей диссертации предпринята попытка систематизации полученных сведений о спектрах степеней на языке сводимостей массовых проблем, введенных Медведевым [5] и Мучником [6]. На этом языке формулируются и новые результаты полученные автором, являющиеся содержательной частью диссертации. В качестве массовых проблем здесь рассматриваются проблемы представимости алгебраических систем. В качестве сводимости этих проблем используется как равномерная сводимость Медведева (сильная сводимость), так и неравномерная сводимость Мучника (слабая сводимость). Данная
4
трак товка позволяет, с другой стороны, рассматривать сводимость но перечислимости, как частный случай сводимости проблем представимости на алгебраических системах специального вида. Отмстим, что при таком рассмотрении тотальные е-степени соответствуют алгебраическим системам, имеющим степень (в смысле Рихтер [31]).
Перейдем теперь к конкретному описанию результатов, полученных в диссертации.
Диссертация разбита на пять глав. Каждая глава разбита на параграфы, количество которых варьируется между тремя и пятью.
Первая глава носит вводный характер. В ней содержатся основные сведения о сводимости па массовых проблемах (параграф 1), о массовых проблемах представимости алгебраических систем (параграф 2), о сводимости по перечислимости (параграф 3), о е-сводимостп алгебраических систем (параграф 4). В параграфе 5 приведены обозначения и терминология, общие для всей диссертации.
Вторая глава посвящена различным описаниям класса тотальных е-отепеней. В параграфе 1 второй главы устанавливается определимость операции скачка е-стененсй и »—► и на языке упорядочения е-степенсй (что решает проблему, поставленную Купером [16] и Сорби [40]).
Для этого, установливается, что предикат х > и' имеет место в е-стсиеиях тогда и только тогда, когда х > и и
(\/а > и)(УЬ > и)(Ус > и)[(Уг > и)[(а и г) П (Ь и г) = г &
(а и и) П (с и г) = г] —* Ь и х = с и х].
Кроме того, устанавливается, что предикат х < и' имеет место в е-степепях тогда и только тогда, когда
(За > и)(ЗЬ > и)(3с > и)(Уг > и)[(а1) г) П(Ы1г) = г&
(Ь II г) П (с и г) = г & (а I) г) П (с I) г) = г & х < а и Ь и с].
5
Следовательно, операция скачка и «—» и' может быть определена в е-степенях посредством конъюнкции УЗУ- и ЗУЗ-формул в сигнатуре частичного упорядочения с-степеней.
Отсюда также следует определимость класса ТОТ(> 0') тотальных е-степеней, расположенных выше (или равных) е-степсни 0'в (что частично отвечает на вопрос Роджерса [32|).
А именно с-степень х является тотальной и расположена выше (или равна) е-стспени 0' тогда и только тогда, когда выполняется конъюнкция формульных иердикатов
(За > 0;:)(ЗЬ > Ос)[х = аиЬ& (Уг)[(а и а) П (Ь и г) = г]]
и
(Уа > 0е) (УЬ > 0е)(Ус > 0С)[(Уя) [(а и г) П (Ь и г) = г] &
(Уг)[(а и г) П (с и г) = г] —» Ъ и х = с и х].
Из определимости класса ТОТ(> 0'е) следует тождественность автоморфизмов полурешетки степеней по перечислимости на е-степенях, расположенных выше О"'.
Кроме Т01ЧЭ, параграф содержит описание множеств, е-сводящихся к е-скачку заданного множества, являющееся аналогом леммы о пределе из классической теории вычислимости для сводимости по перечислимости.
В параграфе 2 второй главы исследуется связь тотальности е-степепи с простейшими принципами обобщенной вычислимости. В частности, установлена эквивалентность тотальности е-степени арифметического множества А с принципами униформизации и редукции, если класс вычислимо перечислимых множеств заменить классом е-сводящихся к А множеств. Результаты этого параграфа получены совместно с Пузаренко (Новосибирск).
В параграфе 3 второй главы устанавливается эквивалентность проблем инвариантности и определимости класса тотальных
6
е-степеней (проблема Роджерса) с проблемой инвариантности и определимости предиката относительной квазиминимальности.
А именно, е-степень а является нетотальной тогда и только тогда, когда выполнен формульный предикат
(Эи)[СКаи и,и)],
что также эквалентно выполнению другого предиката (также являющегося формульным в силу результатов параграфа 1 второй главы)
(Зи)[СЗ(аи и, и) & (аи и)' = и'].
Здесь (^(а, Ь) — предикат относительной квазиминималыюети, означающий, что для каждой тотальной е-степени х < а справедливо х < Ь.
В параграфе 4 второй главы приводится достаточный критерий для того, чтобы тотальная е-степень разлагалась над заданной е-стеиеныо. Данный результат может быть в будущем использован при решении вышеупомянутой проблемы Роджерса. Результаты этого параграфа получены совместно с Арслановым (Казань) и Купером (Лидс, Великобритания).
(Отметим, что в параграфе 2 четвертой главы приведена еще одна характеризация тотальных е-степеней уже на языке сводимостей алгебраических систем.)
Третья глава посвящена развитию методологии построения алгебраических систем спектров степеней с заданными свойствами; в частности, со спектрами степеней, имеющих вид (х | х ^ Ь}. В параграфе 1 третьей главы, носящим вводный характер, излагается используемый в дальнейшем способ кодирования семейств множеств в алгебраические системы.
В параграфе 2 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х £ Ь}; где Ь — произвольная низкая тыорииговая степень.
7
Для этого дается удобное описание спектров семейств, имеющих вид
ЩП,р) = {{п} ®и\пви>&си еП&и^ и(п)},
где 71 — некоторое вычислимо перечислимое семейство, содержащее все конечные множества (например семейство всех конечных множеств или семейство всех вычислимо перечислимых множеств), а V — некоторая вычислимая нумерация В частности, из описания следует, что спектр степеней таких семейств не зависит от выбора семейства 71. Кроме того, выделяются такие нумерации и (названные С5-нумерациями), для которых описание спектра степеней семейства наиболее просто. Вычислимых Сб'-нумераций Л?
множеств оказывается достаточно, чтобы получить спектры степеней вида {х | х ^ Ь), где Ь — произвольная низкая тьюринговая степень: если В € Ь, то V = Ап|И^] будет вычислимой С 5-нумерацией множеств, и спектр степеней семейства 1/У(71, и) в точности будет иметь вид {х | X % Ь}.
Кроме того, в данном параграфе приводится метод, позволяющий строить алгебраические системы сводящиеся друг к другу в слабом смысле, но не сводящиеся в сильном смысле, даже если позволить обагощать системы конечным числом констант. Этот метод найдет применение как в четвертой главе (параграф 2), так и в пятой главе (параграф 3).
В параграфе 3 третьей главы доказана вложимоеть произвольной счетной дистрибутивной решетки в структуры слабых степеней алгебраических систем. Кроме того, здесь найдено некоторое патологическое свойство структуры сильных и слабых степеней. А именно, установлено, что существуют возрастающие цепочки алгебраических систем (относительно рассматриваемой сводимости), имеющие в качестве точной верхней грани некоторую другую алгебраическую систему. При доказательстве этих результатов продолжается изучение
8
спектров степеней семейств >У(7£, и), начатое в предыдущем параграфе. В частности, рассматриваются соотношения между теоретико-множественными операциями на спектрах степеней семейств вида УУ(7£, и) (пересечение и объединение спектров) и операциями на нумерациях (прямая сумма и прямое произведедение). Изучаются также и бесконечные суммы нумераций.
В параграфе 4 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х < Ь}, где Ь — произвольная вычислимо перечислимая тьюринговая степень. В частности, существует алгебраическая система, спектр степеней которой есть {х | х ^ 0'}.
Семейства, исследование в первых двух параграфах третей главы, не могут быть здесь использованы: если 71 — вычислимо перечислимое семейство, содержащее все конечные множества, им — вычислимая нумерация Д^ то спектр степеней семейства УУ(7£, у) содержит все не-низкие степени. Поэтому, здесь рассматриваются семейства вида УУ(Т,еБ), где V — семейство всех областей значений возрастающих примитивно рекурсивных функций (V состоит только из бесконечных множеств), = Ап[1УБ], иВеЬ - вычислимо перечислимое множество (здесь Ь не обязательно является низкой степенью, так что £в вообще говоря не будет' нумерацией Д? множеств). Устанавливается, что спектр семейства УУ(Р,£В) есть {х | х ^ Ъ}.
Четвертая глава посвящена в основном теоретическим результатам, ограничивающим методологию развитую в третьей главе. Одновременно с этим получены некоторые решения проблем, касающихся спектров степеней и различий сильной и слабой сводимости.
В параграфе 1 четвертой главы доказана нерешеточность верхних полурешоток сильных и слабых степеней алгебраических систем.
Для этого устанавливается, что если несравнимые степени ао и ах
9
лежат в спектре степеней счетной алгебраической системы, то этот, же спектр степеней должен содержать также некоторую степень Ь такую, что ао^Ь,аі ^ Ь и Ь' < а(). Оценка Ь' < вместе с результатами из параграфа 1 третей главы, позволяет сделать вывод о том, что две алгебраические системы, имеющие спектры степеней {х | х > а«} и {х | х > аі}, соответственно, не имеют точной нижней грани относительно слабой сводимости, если степени ао и ах несравнимы и являются низкими. Выбирая две конкретные алгебраические системы с указанными выше спектрами степеней, можно распространить данное утверждение и на сильную сводимость алгебраических систем.
В параграфе 2 четвертой главы дается характеризация тотальных е-степеней как е-степеней таких алгебраических систем, сильная и слабая сводимости к которым не отличаются между собой (даже с точностью до конечных обогащений константами).
Для этого для каждой алгебраической системы, не имеющей степени, среди тыоринговых скачков спектра степеней которой имеется наименьший, строится другая алгебраическая система, слабо сводящаяся к первой (то есть неравномерно), но несводщаяся к ней сильно (то есть равномерно), даже если разрешить обогащать системы конечным числом констант.
В параграфе 3 четвертой главы приводится отрицательный ответ на вопрос Миллера [28] об отделимости несравнимых степеней спектрами степеней линейных порядков.
Более того, установлено, что для каждой ненулевой степени а существует такая несравнимая с а степень Ь, Ь' < а', содержащаяся во всех спектрах степеней счетных линейных порядков, в которых содержится степень а.
Приводятся косвенные аргументы в пользу отрицательного ответа па вопрос Доуни [17] о существовании линейных порядков со спек-
10
тром степеней {х | X > 0}.
В параграфе 4 четвертой главы устанавливается существование тыорииговой степени Ь < 0^ такой, что совокупность {х ’ х Ь} не является спектром степеней никакой алгебраической системы.
Для этого, устанавливается, что для каждой пары несравнимых степеней ао и ах существует такая степень Ь < (аоиах)^, что ао ^ Ь, а! Ь, и каждый спектр степеней алгебраической системы, содержащий степени ао и ах должен содержать также степень Ь. В отличие от указанного выше результата из параграфа 1 четвертой главы здесь степень Ь не зависит от фиксированной заранее алгебраической системы со своим спектром степеней. Однако здесь установленная ранее оптимальная оценка Ь' < а'0 ухудшается до Ь < (а0иах)(4) (от оценки скачка степени Ь всего лишь однократным скачком одной из степеней ао и ах до оценки только лишь самой степени Ь четырехкратным скачком точной верхней грани степеней ао и ах). Отметим также, что в силу вышеупомянутого результата из второго параграфа оптимальная оценка сохраняется, если вместо произвольных алгебраических систем ограничится лишь линейными порядками.
' В параграфе 5 четвертой главы основной результат параграфа 4 усиливается, посредством построения степени Ь < 0" такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы.
Для этого, в отличие от предыдущего параграфа, устанавливается, что для каждой ненулевой степени а0 существуют такие степени ах < а2 и Ь < а'о, что ао ^ Ь, ах £ Ь, и каждый спектр степеней алгебраической системы, содержащий степени а0 и ах, должен содержать также степень Ь. При доказательстве этого утверждения используется метод приоритета с бесконечными нарушениями, а также техника работы со степенями по перечислимости.
Пятая глава посвящена изучению е-сводимостей алгебраических
11
систем, основанных на сводимости частичных проблем представимости, введенных Дымент [1]. В частности, оценивается возможность применения методов, разработанных в предыдущих главах для изучения спектров е-стенсией и е-сводимостей алгебраических систем.
В параграфе 1 пятой главы исследуются спектры е-етепеней семейств множеств, натуральных чисел. Доказывается, что спектр е-степеней семейства всех бесконечных вычислимо перечислимых множество совпадает с классом высоких е-степснсй (то есть е-степеней, скачок которых ограничен снизу двойным скачком нулевой е-степени). Для доказательства используется аналог леммы о пределе для сводимости по перечислимости, полученной в параграфе 1 второй главы.
Кроме того, устанавливается, что в отличие от результатов об обычных спектрах степеней семейств из третей главы спектр е-степеней семейств конечных множеств нс может совпадать с классом всех ненулевых е-степеней.
Наконец, доказывается, что спектр е-степеней семейства У\?(£,є) состоит в точности из ненулевых е-степеней (где £ — семейство всех вычислимо перечислимых множеств, и с = А?г[Игп]). Откуда следует, что существует алгебраическая система со спектром е-степеней, совпадающим с классом всех ненулевых е-етепеней. То же самое оказывается верным, если вместо понятии спектра е-степеней использовать понятие расширенного спектра степеней, введенного Сосковым [41].
В параграфе 2 пятой главы исследуется важный частный случай е-сводимости алгебраических систем, связанный с определимостью в допустимых множествах. Здесь проводится сравнительный анализ выразительной мощности £-определений относительно простейших не вычислимо иереслимых семействах вычислимо перечислимых множеств (семейство графиков всюду определенных функций, семейство бесконечных вычислимо перечислимых мно-
12
жеств и проч.). Обсуждается проблема введения операции скачка для Е-степеней семейств. Результаты этого параграфа получены совместно с Пузаренко (Новосибирск).
В параграфе 3 пятой главы полностью описываются все возможные соотношения между сильной сводимостью, слабой сводимостью, сильной о своди мост и, слабой с-сводимостью алгебраических систем, также как и отношения Е-определимости одной системы в конечно-наследственной надстройке другой (см. [2]).
А именно, установлено, что соотношения между рассматриваемыми сводимостями исчерпываются нижеперечисленными:
• из Е-определимости одной системы в конечно-наследственной надстройке другой без параметров следует сильная е-сводимость первой системы ко второй;
• из сильной сводимости следует слабая сводимость;
• из сильной е-сводимости следует слабая е-сводимость;
• из сильной е-сводимости следует сильная сводимость;
• из слабой е-сводимости следует слабая сводимость.
Данное описание остается верным, если в определении сводимостей разрешить обогащать системы конечным числом констант.
Данный параграф завершает исследование рассматриваемых соотношений, начатое Стукачевым в работе [10]. При доказательстве используются результаты из параграфа 1 второй главы, параграфа 1 третьей главы и первых двух параграфов пятой главы.
На защиту выносятся следующие результаты:
• Решение проблемы определимости операции скачка е-степеней, поставленной Купером |1б] и Сорби [40].
13
• Определимость класса тотальных е-степеней, расположенных выше 0'в, что частично решает проблемы Роджерса об определимости класса тотальных е-степеней. Характеризации класса тотальных е-степеней посредством предиката относительной ква-зиминималыюсти, а также на языке сильных и слабых сводимо стей алгебраических систем.
• Решение проблемы Миллера [28] об отделимости несравнимых степеней спектрами степеней линейных порядков.
• Построение алгебраических систем, спектр степеней которых имеет вид {х|х ^ Ь}, где b — низкая или вычислимо перечислимая степень.
• Построение степени b < 0" такой, что совокупность {х|х Ь} не является спектром степеней никакой ал гебраической системы.
• Вложимость произвольной счетной дистрибутивной решетки в слабые степени алгебраических систем с сохраннейшем точных верхних и нижних граней. Нерешеточность верхних иолуреше-ток сильных и слабых степеней алгебраических систем.
• Полное описание всех возможных соотношений между сильной сводимостью, слабой сводимостью, сильной е-сводимости, слабой е-сводимостыо и отношения Е-опредлимости.
Результаты главы 2 опубликованы в работах автора |1],[2], [9J, [10], [11], [13], [15], [18] (см. список публикаций автора по теме диссертации в конце диссертации), главы 3 - в работах [3], [4], [14], [17], главы 4 -в работах [5], [7], [17], главы 5 - в работах [6], [8], [12], [10].
Результаты диссертации но мере их получения докладывались на следующих конференциях:
Logic Colloquium 2001, Вена, Австрия, 6-11 августа 2001 г.
14
Computability and Models, Алматы, Казахстан, 24-28 июня 2002
Logic Colloquium 2002, Мюнстер, Германия, 3-10 августа 2002 г.
British Mathematical Colloquium 2003, Берингем, Великобритания, 7-10 апреля 2003 г.
Алгебра и Анализ 2004, 2 -9 июля 2004, Казань;
Мальцевские чтения 2004, Новосибирск, 16-18 ноября 2004 г.
Methods of Logic in Mathematics 2005, Санкт-Петербург, 18-24 июля 2005 г.
Computational prospects of infinity, Сингапур, лето 2005 г.
Мальцевские чтения 2005, Новосибирск, 15-17 ноября 2005 г.
Computabilty in Europe 2006, Суонси, Великобритания, 30 июня -5 июля 2006 г.
Мальцевские чтения 2006, Новосибирск, 14-16 ноября 2006 г.
Computabilty in Europe 2007, Сиена, Италия, 16-18 июня 2007 г.
Мальцевские чтения 2008, Новосибирск, 11-13 ноября 2008 г.
Итоговые научные конференции Казанского университета, 2002 -2008.
Результаты докладывались на семинаре Алгебра и логика (Новосибирск, ИМ СО РАН, рук. - академик Ершов Ю.Л.), логическом семинаре Отделения Математики университета Лидса (Великобритания, рук. - проф. С. Вейнсф, проф. С.В. Купер), логическом семинаре математического факультета Висконсинекого университета (США, рук. проф. С. Лемпп), семинаре по теории вычислимости Чикагского университета (США, рук. проф. Р. Соар), логическом семинаре математического факультета университета Ватерлоо (Канада, рук. - Р. Виллард). В целом работа доложена на семинаре по теории вычислимости на механико-математическом факультете Казанского государственного университета (рук. - проф. М.М. Арсланов).
Автор выражает глубокую благодарность М.М. Арсланову за постоянное внимание к работе и плодотворные беседы, способствовав-
15
шие улучшению диссертации.
10
Глава 1
Массовые проблемы представимости алгебраических систем
1.1 Массовые проблемы и решетка Медведева
Массовой проблемой (по Медведеву) называется произвольная сово-
ных чисел со. Элементы массовой проблемы называются также методами ее решения. Сопоставляя каждое множество .V С ш с его характрис/гической функцией \х
будем считать, что элементами (методами) массовых проблем могут быть и подмножества множестве всех натуральных чисел со.
На классе массовых проблем рассматриваются две алгоритмические сводимости. Если А и В — массовые проблемы, то сильная (или равномерная) сводимость А <3 В имеет место, если существует единая алгоритмическая процедура, порождающая методы из А по произвольному методу из В; более формально, если существует тьюрин-говый оператор Ф, такой, что Ф9 Є А для каждого д € В.
купноеть всюду определенных функций па множестве всех натураль-
Слабая (или неравномерная) сводимость А <ю В имеет место, если к каждом)' методу из В может быть применена некоторая алгоритмическая процедура, порожающая метод из А; то есть для каждого метода g Є В существует метод / Є А, такой, что / <Т д.
Обе сводимости индуцируют степенные структуры на классе массовых проблем, соответствующие степени называются сильными (слабыми) степенями трудности. Обе структуры являются дистрибутивными решетками относительно следующих операций на массовых проблемах
АлВ = {/ф0|/єА&0ЄВ}
(индуцирует наименьшую верхнюю грань степеней трудности проблем А и В)
А V В = {0 * / | / Є A} U {1 * g | g Є В}
(индуцирует наибольшую нижнюю грань степеней трудности проблем А и В). Здесь функции вида / 0 д, 0 * /, 1 * д заданы так: /0.7(27?) = /(п),
/0<?(*2п+ 1) =g(n),
0*/(0) = 0, 0*/(» + 1) = /(п),
1 * .7(0) = 1, 1 * #(n + 1) = д(п) для всех п Є to.
Отметим, что решетка сильных степеней D.s называется также решеткой Медведева. Решетка слабых степеней называется также решеткой Мучника.
Массовая проблема АЛВ соответствует проблеме решения проблемы А и проблемы В. Массовая проблема AVB соответствует проблеме решения проблемы А или проблемы В. Наименьшим элементом решеток сильных и слабых степеней трудности является степень 0. состоящая из массовых проблем, имеющих хотя-бы один вычислимый метод (легко видеть, что для таких проблем понятия сильной и
18
слабой сводимости совпадают). Наибольшим элементом формально считается степень 1, соответствующая проблеме, не имеющей методов. то есть пустому множеству функций. В этих решетках также имеется элемент, наименьший среди всех отличных от 0 степеней. В обоих случаях такой элемент является сильной (слабой) степенью трудности проблемы, состоящей из всех невычислимых методов:
N0 = {/ | ш —> и | / не является вычислимой функцией}.
Отметим, что в слабых степенях теоретико-множественное объединение АиВ также индуцирует наибольшую нижнюю грань соответствующих степеней трудности, поскольку
А V В АиВ.
Спектром степеней проблемы А назовем совокупность тчоринговых степеней, относительно которых хотя-бы один метод из А становится вычислимым:
Эр (А) = {х | (3/ е А)[/ <т х]}.
Например, спектром степеней проблемы N0 является совокупность всех ненулевых степеней. Ясно, что спектр степеней проблемы А полностью описывает свойства этой проблемы относительно слабой сводимости. Вол ее того, для проблем А и В имеет место
А <ШВ -<=> Эр (В) С Бр (А),
Эр (А Л В) = Эр (А) П Эр (В),
Эр (А V В) = Эр (А и В) = Эр (А) и Бр (В),
так что вр индуцирует изоморфизм решетки слабых степеней и дуальной решетки замкнутых вверх классов степеней относительно включения.
Отметим, что трудно назвать произвольное множество функций-методов (например N0) математической проблемой, поскольку не
19