Сложность вычислений в алгебраических системах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Рыбалов, Александр Николаевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Омск
МЕСТО ЗАЩИТЫ
|
||||
|
2004
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Рыбалов Александр Николаевич
СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ В АЛГЕБРАИЧЕСКИХ СИСТЕМАХ
01.01.06 - математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Работа выполнена на кафедре математической логики и логического программирования Омского государственного университета
Научный руководитель: доктор физико-математических наук, профессор
Владимир Никанорович Ремесленников
Официальные оппоненты: доктор физико-математических наук,
профессор
Андрей Сергеевич Морозов
доктор физико-математических наук, профессор
Леонид Матвеевич Мартынов
Ведущая организация: Новосибирский государственный технический университет.
Защита состоится "О .января 2005 г. в /У часов на заседании диссертационного совета К212.179.01 при Омском государственном университете по адресу: 644077, Омск, пр. Мира 55а.
С диссертацией можно ознакомиться в библиотеке ОмГУ. Автореферат разослан . декабря 2004 г.
Ученый секретарь диссертационного совета, доктор физ.-мат. профессор
В.А. Романьков
Общая характеристика работы
Актуальность темы. Классическая теория сложности вычислений берет свое начало с середины 20 века, когда появились первые компьютеры. В уже существовавшей к тому времени теории алгоритмов вычислительные процессы рассматривались без ограничения на ресурсы, которые возникают при реализации вычислительных устройств на практике. Главными такими физическими ресурсами являются время выполнения алгоритма и пространство (память), требуемая вычислительному устройству в процессе выполнения алгоритма. В теории сложности под алгоритмом как правило понимается машина Тьюринга (МТ), т.к. эта вычислительная модель очень хорошо отражает свойства реальных компьютеров. Машины Тьюринга могут вычислять функции вида
или распознавать множества вида где
некоторый конечный алфавит (обычно Е = {0,1}). Время работы ijVi(x) МТ М на входе х € Е* - это число шагов МТ на входном слове х до ее остановки (iji/(i) = оо, если машина не останавливается). Пространство Зм(х) машины М н а - это число ячеек ее рабочей ленты, используемых в вычислении.
Любую проблему, решаемую на компьютере, можно при помощи кодирования представить как проблему распознавания некоторого множества А строк подходящего конечного алфавита. С практической точки зрения наиболее важной информацией о множестве А является оценка сверху времени или пространства распознающего А алгоритма в зависимости от размера входных данных. Так как в теории сложности входами алгоритмов являются строки, то естественный размер входа - это длина входного слова. Таким образом, возникает понятие сложностного класса по времени:
TIME(f) = {А С Е* : существует МТ М, распознающая А
такая, что для любого имеет место и, аналогично, по пространству
: существует МТ М, распознающая А такая, что для любого х имеет место
где / : N —> N - некоторая возрастающая функция. Большинство практических алгоритмов имеют полиномиальную оценку времени, поэтому, начиная с работ [15] и [18], выделяют следующие важные классы
PSPACE = (J SPACE{nk + к).
С 1970-х годов в теории сложности вычислений появляется новая вычислительная модель - недетерминированная машина Тьюринга (НМТ). В НМТ есть так называемые недетерминированные состояния, из которых возможен переход сразу в несколько последующих состояний. На одном и том же входе такая машина может иметь несколько вычислительных путей (т.е. последовательностей состояний, возникающих в процессе работы машины). Таким образом, время и пространство такой машины М на входе X зависят от пути да, по которому происходит вычисление: tM<T(x) и sm,t{x)- Определяются недетерминированные сложностные классы по времени
NTIME(f) = {А С £*: 3 НМТ М такая, что х € А & Зт -
принимающий выч. путь Мна х такой, что tjnf T{x) < /(|я|)} и по пространству
такая,
принимающий выч. путь М на такой, что
Соответствующие полиномиальные классы определяются аналогично детерминированному случаю:
NPSPACE = Q NSPACE(nk + к).
С момента своего появления эти классы активно изучаются. В 1971 г. С.Кук в статье [16] доказал, что в классе NP существуют полные относительно полиномиальной сводимости множества
i ЦНМ., i
• »сгйиМм | 4
и привел пример такого множества (проблемы), связанной с выполнимостью булевых формул. В 1972 г. Р. Карп в статье [23] доказал, что многие практически важные комбинаторные проблемы являются iVP-полными. ЛЛевин в работе [5] независимо от них получил аналогичные результаты в его терминах так называемых универсальных переборных задач. В 1972 г. У.Сэвич в работе [31] показал, что PSPACE = NPSPACE. В 1975 г. Р.Ладнер в работе [25] доказал, что при условии истинности существуют множества, не являющиеся полными относительно полиномиальной сводимости. В 1975 г. Бэйкер, Джилл и Соловэй в [9] привели пример оракулов А и В таких, что РА = NPA, но Рв ф NPB. Но, несмотря на многочисленные усилия, вопрос о совпадении классов Р и NP до сих пор остается нерешенным.
С 1980-х годов активно развивается обобщенная вычислимость, обобщающая классическую теорию алгоритмов на произвольную алгебраическую систему 21 = {А, а). Если в этой теории в качестве системы взять систему с конечным основным множеством А (например, бинарное поле GF(2)), то получится классическая тьюрингова вычислимость.
Можно выделить два основных подхода к построению такой теории: формульный и машинный. В формульном подходе вычислимые функции, предикаты и множества определяются при помощи специальных формул некоторого расширения сигнатуры а. Например, в Е-определимости (Ю.Л.Ершов [4], Дж. Барвайс [10]) вводится семейство наследственно конечных множеств
HFq(A) = A, HFn+1(A) = Vu{HFn(A)),
где ТЫ{М) — семейство всех конечных множеств с элементами из М. Далее вводится алгебраическая система НР(Щ = {HF{A),<Ti) с сигнатурой <7i = a U {¡3, £2}, где 0 — константный символ, интерпретируемый как пустое множество, а £2 — предикатный символ, интерпретируемый как предикат принадлежности. Класс формул строится из атомарных формул сигнатуры при помощи логических связок, навешивания квантора существования и так называемых ограниченных кванторов Vz € t И Зх £ t, где t - терм сигнатуры <j\. Теперь функция / : HF{A)k -> HF{A) -
2-функция (вычислимая в данном подходе), если ее график определим некоторой 2-формулой.
В машинном подходе вычислимые объекты определяются при помоши некоторых абстрактных вычислительных устройств, которые могут использовать в вычислениях функции, предикаты и константы сигнатуры а или некоторого ее расширения. Так, в S-вычислимости Хеммерлинга ([22]) — это так называемые S-машины, в подходе Ашаева, Беляева и Мясникова ([1]) — это машины с неограниченными регистрами (МНР).
5-вычислимость была предложена Хеммерлингом в работе [22] и является непосредственным обобщением подхода Блюм, Шуба и Смейла ([14]) к вычислимости над кольцами и полями. Вычислимые функции определяются при помощи 5-машин, которые работают с непустыми строками элементов из основного множества А. Эти вычислительные устройства являются обобщением машины Тьюринга и состоят из рабочей строки, программы и конечного набора указателей на элементы рабочей строки. Инструкции программы позволяют записывать в элемент строки, на который указывает указатель значения функций и констант сигнатуры ст, совершать условные переходы, зависящие от истинности предикатов сигнатуры а, а также позволяют сдвигать указатели, добавлять и удалять элементы в рабочую строку. S-машины могут вычислять функции вида - множество всех
непустых конечных строк с элементами из А.
Вычислимость над списочной надстройкой была предложена Ашаевым, Беляевым и Мясниковым в 1993 году в работе [1]. В этом подходе используется введенная в работе [3] списочная надстройка HL{A) основного множества А:
где L(M) - множество всех конечных списков с элементами из М. Далее расширяется сигнатура а до сигнатуры <г* добавлением функций для работы со списками: cons - добавление одного списка в конец другого, tail - отбрасывание первого элемента списка, head - взятие первого элемента списка, а также добавлением константы nil, интерпретируемой как пустой список. В
итоге получается система НЬ(Щ = (НЬ(А),а*), которая называется списочной надстройкой системы 21. Вычислимые функции вида / : НЬ(А) —» НЬ(А) определяются при помощи машин с неограниченными регистрами (МНР), которые в своих командах используют функции, предикаты и константы сигнатуры а*.
Общей чертой всех этих подходов является введение некоторой дискретной структуры над основным множеством, позволяющей получать вспомогательные конструкции из элементов А, необходимые для развития теории вычислимости в системе 21. Для 2-определимости - это наследственно конечные множества Н¥(Л), для 5-вычислимости - это строки элементов из А, для вычислимости над списочной надстройкой - это списочная надстройка БЬ(Л). Более того, в некотором смысле эти подходы являются эквивалентными. В работе [7] показано, что 5-вычислимость и вычислимость над списочной надстройкой, ограниченная на списки Ь\(А), приводят к одному и тому же классу вычислимых функций вида (строки элементов из А можно отождествлять с - списками глубины 1 из элементов А). В работе [8] доказана эквивалентность 2-определимости и подхода Моско-вакиса ([28]), а также эквивалентность вычислимости над списочной надстройкой и подхода Московакиса в случае примитивно-рекурсивных функций.
Теория сложности вычислений над произвольными алгебраическими системами берет свое начало с работы Блюм, Шуба и Смейла [14], в которой она была развита на основе теории вычислимости над кольцами и полями. Отметим основные моменты этого подхода. Пусть К — (А, {+, —, Х,Сд}) - некоторое кольцо, где - все элементы множества А, добавленные в качестве констант и интерпретируемые сами собой. Входами, с которыми работают вычислительные устройства, являются строки элементов из Я. Под размером строки понимается ее длина - таким образом при этом происходит отвлечение от природы элементов множества А, которая может быть неконструктивной (например, комплексные и вещественные числа), а внимание сосредотачивается на дискретных структурах (строках, списках и т.д.). Абстрактное вычислительное устройство - это машина для алгебраической системы Я. Время работы такой машины -число инструкций, выполненных от начала работы до ее остановки. В частности, операции с элементами кольца происходят за
единицу времени - опять игнорируется природа элементов кольца. Класс Р над R состоит из множеств строк, распознаваемых •BSS-машинами за полиномиальное время. Недетерминированные BSS-шшяки допускают так называемые инструкции подсказки, которые присваивают элементу рабочей строки произвольный элемент из А. После выполнения такой инструкции, машина имеет более одного варианта дальнейшей работы. С помощью недетерминированных BSS-иашап дается определение к л а с A'i^ н а -логичное классическому. Позже в работе [17] был определен класс DNP аналогично классу NP, но с помощью более узкого класса недетерминированных BSS-машин, в которых вместо инструкций подсказки используются недетерминированные переходы - команды перехода сразу к двум последующим инструкциям. Для колец с более чем одним элементом в А недетерминированные переходы можно смоделировать инструкциями подсказки, а потому для таких систем имеет место включение Другие определения классической теории сложности вычислений подобным образом переносятся на кольцо R. В случае, когда кольцо R конечно, получается классическая теория вычислительной сложности над строками из конечного алфавита. Основной упор в работе [14] делается на поле комплексных чисел С и упорядоченное поле действительных чисел В случае комплексных чисел, например, приведен следующий пример ./VP-полного множества:
где code - некоторая кодировка полиномов с комплексными коэффициентами строками комплексных чисел. Были также поставлены вопросы о совпадении классов Р и NP над полями С и R, первому из которых посвящена работа [13]. В дальнейшем подход Блюм, Шуба и Смейла был обобщен Хеммерлингом на произвольную алгебраическую систему в работе [22].
Некоторые из результатов классической теории сложности вычислений были перенесены на поля и произвольные алгебраические системы. Прежде всего, это теорема Кука-Левина о существовании iVP-полных проблем, перенесенная Блюм, Шубом и Смейлом на поле С, и Хеммерлингом на некоторые типы алгебраических систем в статье [22]. Так же можно отметить результат Меера и Малаховича в [26], переносящий теорему Ладнера на поле С, а также работу Бен-Давида, Меера и Милю [И], в которой
доказано, что теорема Ладнера при некоторых дополнительных условиях имеет место над полем К. с порядком. Эмерсон в работе [19] переносит классическую теорему Бэйкера-Джилла-Соловэя на упорядоченное поле К.
Много исследований было посвящено аналогам проблемы Р = NP1 в различных алгебраических системах. Меер в 1992 г. в работе [27] доказал, что Р ф ЫР над аддитивной группой действительных чисел (фактически он доказал, что Р ф /?ЛГР). В дальнейшем Койран в [24] упростил доказательство этого факта. Гасснер в 2002 г. в статье [21] дала доказательство неравенства Р ф БИР для всех бесконечных абелевых групп. Прунеску в [29] упростил его. Пойзат показал, что для бесконечных алгебраически незамкнутых полей имеет место Р ф ЛТР (этот результат опубликован в монографии [12] в 1996 г.). В частности, из этого следует, что для неупорядоченного поля действитель-
ных чисел. Прунеску в 2003 г. в статье [30] доказал неравенство Р ф DNP для бесконечных булевых алгебр. В 2004 г. в работе [32] автором было доказано, что Р ф РЛГР для кольца вещественных матриц с константами: нулевой и единичной матрицей. Проблема Р = -ОЛ^Р? для полей С и И, а также проблема Р == Л/Р? для поля С и упорядоченного поля Ц. до сих пор нерешены. В работе [13] установлены связи между истинностью неравенства , над С и некоторыми теоретико-числовыми гипотезами. Так же можно отметить работу [20], в которой показано, что Р ф ИР над упорядоченной аддитивной группой действительных чисел тогда и только тогда, когда Р ф ИР в классической теории.
. Цель работы. Основной целью нашего исследования является развитие нового подхода к сложности вычислений в произвольной алгебраической системе на основе вычислимости над списочной надстройкой, предложенной Ашаевым, Беляевым и Мясниковым в [1]. В частности, обобщение классической теоремы Кука-Л евина о существовании ЖР-полных множеств. Сравнение нашего подхода с подходом Хеммерлинга на строках и моделирование классической тьюринговой теории сложности вычислений. Также нас интересуют проблемы типа и истинность некоторых
классических фактов в конкретных алгебраических системах (в полях С и Я, матричных кольцах).
Методы исследования. В работе используются и развиваются методы теории алгоритмов и теории сложности вычислений,
логики и алгебры.
Теоретическая значимость. Работа имеет теоретическое значение. Получено обобщение теоремы Кука-Левина в рамках нового подхода к вычислительной сложности в алгебраических системах. Исследована проблема Р = NP1 над кольцом вещественных матриц и ее релятивизованная версия над полем С.
Практическая ценность. Результаты данной диссертации могут быть использованы при чтении спецкурсов по теории алгоритмов и вычислительной сложности, при подготовке учебных пособий.
Апробация работы и публикации. Основные результаты для диссертации опубликованы в работах [32, 33, 34, 35, 36], были доложены на алгебраическом семинаре в Омском госуниверситете, а также на Международной конференции "Мальцевские чтения" (Новосибирск, 2003, 2004) и Международной конференции "Алгебра, логика и кибернетика" (Иркутск, 2004).
Структура и объем работы. Диссертация изложена на 95 страницах, состоит из введения, пяти глав и списка литературы. Главы разбиты на параграфы.
В первой главе даются сведения из классической теории сложности вычислений. Излагаются подход Ашаева-Беляева-Мяснико-ва (вычислимость над списочной надстройкой) к обобщенной вычислимости и подход Хеммерлинга (5-вычислимость) к вычислимости и сложности вычислений над произвольной алгебраической системой.
Во второй главе даются основные определения теории сложности вычислений, основанный на вычислимости над списочной надстройкой. Определяются полиномиальные сложностные классы Р, DNP, NP, PSPACE, DNPSPACE, NР SPACE над произвольной алгебраической системой. Приводятся примеры некоторых полиномиальных функций.
В третьей главе доказывается, что на строках из А наш подход и подход Хеммерлинга полиномиально эквивалентны (теоремы 3.1 и 3.2). То есть для функции, вычисляемой МНР в нашем подходе, найдется вычисляющая ее и наоборот. Причем время
работы при таких переходах возрастет не более, чем полиномиально. Как следствие из этого результата моделируется классическая тыорингова сложность внутри любой алгебраической системы (следствие 3.1).
В четвертой главе приводятся примеры полных относительно полиномиальной сводимости проблем в классах ^ и DNP для произвольной алгебраической системы. Для класса ЫР это аналог классической теоремы Кука-Левина о ЫР-полноте проблемы выполнимости булевых формул (теорема 4.1). Для класса DNP это проблема, связанная с так называемыми вычислительными схемами, которые являются обобщениями классических булевых схем (теорема 4.2).
В пятой главе исследуются проблемы сложности вычислений в некоторых алгебраических системах. Доказываются неравенства: Р ф ИИР над кольцом вещественных матриц (теорема 5.1), Р ф РБРАСЕ и РБРАСЕ ф БМРБРАСЕ над неупорядоченным полем К (теоремы 5.4 и 5.3), Р2 ф ЭИР^ над полем С (теорема 5.5). Последнее неравенство переносит на С одно из утверждений классической теоремы Бэйкера-Джилла-Соловэя. Также строятся два множества из над неупорядоченным полем действи-
тельных чисел которые не сводятся друг к другу за полиномиальное время (теорема 5.2). Тем самым доказывается безусловный аналог теоремы Ладнера в этой системе.
На защиту выносятся следующие результаты:
— полиномиальная эквивалентность нашего подхода и подхода Хеммерлинга для строк,
— обобщение теоремы Кука-Левина для произвольной алгебраической системы с конечным числом функций и предикатов в сигнатуре,
— соотношения между полиномиальными классами сложности в классических алгебраических системах: кольцо вещественных матриц, неупорядоченное поле вещественных чисел, поле комплексных чисел.
Содержание работы
В параграфе 2.1 даются основные определения теории сложности вычислений в алгебраической системе 121 = {А, а).
Определение 2.1. Функция размера sizem : НЦА) —ï N
определяется следующим образом
( \ f 1> ес 9izeHL(a) = |
если а = nil или а € Л,
sizem(ai) +1, при а = (аь... ,а„).
Определим натуральные числа в списочной надстройке: пяь = {nil,... ,nil).
п раз
В дальнейшем мы будем опускать индекс у элементов N#£ и вместо пщ писать просто п, так как из контекста будет понятно, где обычные натуральные числа, а где списки.
Дается определение функции времени работы МНР. Определение 2.2. По МНР М над ЯЬ{Щ определим функцию
tM:HL{A)->Nl)oo
— врет работы М. Если на входе х 6 HL(A) машина не останавливается, то полагаем = оо. Иначе рассмотрим т(х) = {/],... ,/„} - вычислительный путь М на х. Положим
п
tu,r(x) = ^гг'те(Д), *=1
где time(Ih) = 1, если h ~ одна из следующих команд
Rm := с, с € о* — константа, Rm := • ■ • , Ru), где f £ о - функция, if P{Ril,... , Ri) goto q, где P £ о — предикат, if ? goto q,
time(Ih) = sizeni{a{), если It - одна из команд
Rm := Ri, Rm := tail(Ri), Rm := head(Ri), Ri := guess, if Ri e О goto t,
где ai — содержимое регистра Ri, О С HL(A) — оракул. Наконец
time{Ik) = sizeHi(ai) + sizesi(ar), если Ik — одна из команд
Rm := cons(Ri,Rr), if Ri = Rr goto t,
где а;, аГ — содержимые Ri,RT. Положим теперь Ьщ(х) = для детерминированной МНР М. Для недетерминированной МНР М мы будем использовать полную запись t^T{x). Определяется функция пространства МНР. Определение 2.7. Для МНР М определим функцию пространства '
sM:#I(A)->NUoo
следующим образом. Если М не останавливается на х £ HL(A), полагаем sm(x) = оо, иначе
sm(x) — шах {size[Rk)}, k=
где Ri — регистры МНР М и максимумы по их содержимому берутся за все время работы машины.
Затем определяются полиномиальные сложностные классы (машины в этих определениях предполагаются нерелятивизованны-ми).
Определение 2.3. Будем говорить, что МНР М полиномиальна, если существует полином р такой, что
Vx € HL(A) М останавливается на х и Ьм{х) < p{sizem(x)).
Определение 2.4. Множество П С HL(A) принадлежит классу Рццщ, если его характеристическая функция вычислима некоторой полиномиальной МНР.
Определение 2,5. Множество П С НЬ{А) лежит в классе DNPhl(%), если существует недетерминированная МНР первого рода М и полином р такие, что
х £ П & существует вычислительный путь т машины М на х
такой, что tu,T[x) < p{sizegi(x)) и М на нем выдает 1.
Определение 2.6. Множество П С HL(A) принадлежит классу NPj{i(%), если существует недетерминированная МНР второго рода М и полином р такие, что
i 6 П» существует вычислительный путь т машины М на х
такой, что tf,;~(x) < p(sizenL(x)) и М на нем выдает 1.
Определение 2.8. Класс РБРАСЕдцщ образуют подмножества HL(A), чьи характеристические функции вычислимы МНР
с функциями пространства, ограниченными полиномиально от размера входа.
Определение 2.9. Множество Q С HL(A) лежит в классе DNPSPACEgi(a)j если существуетнедетерминированнаяМНР первого рода M и полином р такие, что
х существует вычислительный путь Т машины M на х
такой, что зд/1Т(х) <p(stze#£(x)) и M на нем выдает 1.
Определение 2.10. Множество П Ç HL(A) лежит в классе NPSPACEhlw) I если существуют полиномр и недетерминированная МНР второго рода M такие, что
существует вычислительный путь машины M на
такой, что 8м,г(х) < p{sizeai(x)) и M на нем выдает 1.
Релятивизованные классы Рцц<щi и МРдцщ определя-
ются аналогично обычным полиномиальным классам при помощи МНР с оракулами. .
В главе 3 доказываются теоремы о полиномиальной эквивалентности вычислимости над списочной надстройкой и 5-вычис-лимости Хеммерлинга. Множество всех строк А+ с элементами из А можно отождествлять с L\(A) — множеством списков глубины 1 над А, а функции вида / : рассмотренные Хеммер-
лингом в [22], интерпретировать как функции вида / : Li(A) НА).
Теорема 3.1. Пусть M — детерминированная S-машина, тогдаможноэффективно построить детерминированную МНР М*, вычисляющую ту же самую функцию, причем
Чх€ A+tM.(x) = 0{tu{x)3).
Теорема 3.2. Пусть 21 - алгебраическая система, в сигнатуре которой есть хотя бы две константы. M - детерминированная МНР, вычисляющая функциюА+. Тогдаможноэффективно построить детерминированнуюS-машинуМ*, вычисляющую f, причем
В главе 4 определяются полиномиальная сводимость множеств и полные множества в классах МРдцщ и ОМР^цщ над алгебраической системой с конечным числом функций и предикатов в сигнатуре.
Определение 4.1. Пусть 51,5г С НЬ(А). Множество 5] полиномиально сводится к множеству 5г, если существует такая функция г : НЬ(А) -> НЬ[А), вычислимая полиномиальной МНР, что для всех х € НЬ{А) х € й г(х) €
Определение 4.2. Множество Б С НЬ{А) —ИРццщ-полное (О МРнцъу полное), если I? £ ЫРнц<а) £ ИЫРнцщ) и любое множество В из NPццщ (из полиномиально сводит-
ся к $«
Далее определяется кодировка термов а списками из НЬ(А): = (0,0.
а(с) = {1, с), с — элемент из НЬ(А),
а(Леас^)) = {2,а(()), где ^ - терм,
а(<аг7(*)) = (3,а(<)), где < - терм,
а(сопв(^,«2)) = (4,«(«!),а(<2)>, где - термы,
а(/>(*1> • • • > = (5,1, а{Ь),.... а(*„)), /< - функция из а.
Кодирование бескванторных формул Р осуществляется так:
,(„)) = {1,1, Д,- предикат из (Г,
Ф) = (2,/?(Ф)>,
/?(Ф1ЛФ2) = {3,/?(Ф1),^(Ф2)), V Ф3) = <4,>9(ФД),/?(Ф2»,
Определяется аналог классического множества выполнимых булевых формул.
БАТнцщ = { /?(Ф), где Ф - формула с параметрами из НЦА)
такая, что Эа1,... ,а„ 6 ЯДА) ЯЦй) |= Ф(а15... ,а„)
и для всех I имеет место зиея^а,-) < 5гге#£(/?(Ф)) }.
Доказывается обобщение классической теоремы Кука-Левина. Теорема4.1. 5ЛТяЦЯ) —ИРшщ-полноемножество. Дается определение вычислительной схемы над НЬ(А) — обобщения понятия классической булевой схемы.
Определение 4.3. Вычислительная схема С над HL(21) — конечный набор переменных y¡, i = 1,... ,п и условных присваиваний (одно для каждого i > 1):
fu ->• Vi := tu, ■ • • iVitf № •'= tu*,
где<pn,...,<p¡t¡ - бескванторные формулы сигнатуры а* от переменных yj, i <i с параметрами из HL(A), a tu,... ,í)(t, - термы а* от переменных y¡, j < i или элементы HL(A).
Значение переменных схемы С на х € HL{A) определим по индукции. Через уг(х) будем обозначать значение переменной y¡ на х. Полагаем yi(x) = х. Пусть для i — 1,... , s — 1 <п значения у, уже определены, а уе определяется присваиванием
<Р<1 У» t¡i,... ,<psk, У„ •■= t¡k,.
Тогда y,(x) равно tsj от значений уже определенных переменных Ук(х), к < s, где j - первый индекс, для которого ips¡ истинно, если же такого j нет, значение 1/1(2) равно y3-i (х). Значение С(х) вычислительной схемы С на х - это значение ее последней переменной У*{х).
Далее определяется кодировка 7 вычислительных схем элементами HL(A). Пусть А\,..., Ап - все условные присваивания схемы С. Тогда 7(С) = (í(Ai),... ,5(Ап)), где код í(A¿) присваивания А{
V.1 Vi ti 1, • • • , Viit Vi := tiki
определим так:
J(A¡) = (J3{ya),a(ta),... ,/%*)>«(**)>•
Выделяется класс гладких вычислительных схем. Определение 4.4. Вычислительная схема С — гладкая, если для любого х € HL(A) такого, что sizejji(x) < size&i(j(€)), для всех переменных y¡ из С верно sizegi(yi(x)) < si ze/¡¿(-у (<£)).
СШНцщ = {7(С) : С- такая гладкая вычислительная схема, что
Зх е 1х({0,1}) sizeHL(x) < sizeHL{?(€)) и С(ле) = 1}.
Напомним, что L\ ({0,1}) - множество всех конечных списков глу-. бины 1 из элементов и 1 hl-
Теорема 4.2. СШццщ — DNРнц%уполное множество.
В главе 5 изучаются вопросы сложности вычислений в конкретных алгебраических системах. В параграфе 5.2 рассмотрено кольцо вещественных матриц
где О — нулевая матрица, Е — единичная матрица, М„( 1) — множество вещественных матриц размера п > 1. Теорема 5.1. РНцщ ф DNPHL{m).
В параграфе 5.3.1 доказан _ безусловный аналог теоремы Ладне-ра для неупорядоченного поля действительных чисел
И = (М,{0,1,+,-,х,/}).
Теорема 5.2. В NPhl(й) \ Рнц<л) существуют множества, не являющиеся МРдц^-полными.
В параграфе 5.3.2 рассмотрены полиномиальные классы по пространству для неупорядоченного поля 9t.
Теорема 5.3. РБРАСЕНц<я) Ф DNPSPACEHL^y Теорема 5.4. Рн1(Я) ф PSPACEHm. В параграфе 5.4 рассмотрены полиномиальные классы с целочисленным оракулом Z над полем комплексных чисел
С = (С,{0,1,+,- х,/}>.
Теорема 5.5. P%m*DNI*m.
Список литературы
[1] Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика, Т.32, №4, С. 349-386, 1993.
[2] Вялый М., Китаев А., Шень А. Классические и квантовые вычисления. М.:МЦНМО, ЧеРо, 1999.
[3] Гончаров С.С., Свириденко Д.И. ^-программирование. Логико-математические проблемы МОЗ (Вычислительные системы, вып. 107), Новосибирск, С. 3-29,1985.
[4] Ершов Ю.Л. Определимость и вычислимость. Новосибирск: Научная книга, 1996.
[5] Левин Л. Универсальные переборные проблемы // Проблемы передачи информации, 9(3), С. 265-266, 1973.
[6] Романов Р.В. Некоторые проблемы обобщенной вычислимости. Препринт №98-03, С.1-32, Омск, 1998.
[7] Рыбалов А.Н. Два подхода к обобщенной вычислимости на строках. Препринт №2000-02, С. 1-26, Омск, 2000.
[8] Рыбалов А.Н. Три подхода к обобщенной вычислимости. Препринт №01-03, С. 1-28, Омск, 2001.
[9] Baker Т., Gill J., Solovay R. Relativizations of the P=?NP question // SIAM Journal on Computing, 4, pp. 431-442, 1975.
[10] Barwise J. Admissible sets and structures. Springer, 1975.
[11] Ben-David S., Meer K., Michaux С. A note on non-complete problems in NPr // Journal of Complexity, vol. 16, №1, pp. 324-332, 2000.
[12] Blum L., Cucker F., Shub M., Smale S. Complexity and Real Computation. Springer, 1998.
[13] Blum L., Cucker F., Shub M., Smale S. Algebraic Settings for the Problem // Lectures in Applied Mathematics, vol 32, pp. 125-144, Amer. Math. Soc. 1996.
[14] Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines // Bull. Amer. Math. Soc, 21, pp. 1-46,1989.
[15] Cobham A. The intrinsic computational difficulty of functions. // Proceedings of the 1964 Internationnal Congress for Logic, Metodology and Philosophy of Science, pp. 24-30. Elsevier/North-HoIIand, 1964.
[16] Cook S. The complexity of theorem-proving procedures // Proceedings of 3d Annual ACM Symposium on Theory of Computing, pp. 151-158, 1971.
[17] Cucker F., Matamala M. On digital nondeterminism // Math. Syst. Theory, 29, pp. 635-647, 1996.
[18] Edmonds J. Minimum partion of a matroid into independent subsets. // J. Res. Nat. Bur. Standarts Sect. B, 69, pp. 67-72,1965.
[19] Emerson T. Relativization of the P=?NP question over the reals (and other ordered rings) // Theoretical Computer Science 133, pp. 15-22, 1994.
[20] Fournier H., Koiran P. Are lower bounds easier over the reals? // Proc. 30th ACM Symposium on Theory of Computing, pp. 507-513, 1998.
[21] GaBner C. The P - DNP problem for infinite abelian groups // Journal of Complexity, 17, pp. 574-583, 2001.
[22] Hemmerling A. Computability and complexity over structures // Math. Logic Quarterly, 44, No.l, pp. 1-44, 1998.
[23] Karp R. Reducibility among combinatorial problems // Complexity of Computer Computations, pp. 85-103, NY, 1972.
[24] Koiran P. Computing over the reals with addition and order // Theoretical Computer Science, 133, pp. 35-47, 1994.
[25] Ladner R. On the structure of polynomial time reducibility // Journal of the ACM, vol. 22, pp. 155-171,1975.
[26] Malajovich G., Meer K. On the structure of NPC // SIAM Journal on Computing, vol. 28, №1, pp. 27-35, 1999.
[27] Meer K. A note on - result for a restricted class of real machines // Journal of Complexity, 8, pp. 451-453, 1992.
[28] Moschovakis Y.N. Abstract first order computability // Trans. Amer. Math. Soc, vol. 138, pp. 427-464, 1969.
[29] Prunescu M. A model-theoretic proof forP ^ NP over all infinite abelian groups // Journal of Symbolic Logic, Vol. 67, №.1, pp. 235-238, 2002.
[30] Prunescu M. for all infinite Boolean algebras // Math. Logic Quarterly, 49, №.2, pp. 210-213, 2003.
[31] Savitch W. Relationships between nondeterministic and deterministic tape complexities // Journal of Computer and System Sciences, 4(2), pp. 177-192,1970.
Список работ автора по теме диссератации
[32] Rybalov A. On the P-NP problem over real matrix rings // Theoretical Computer Science, Vol. 314/1-2, pp. 281-285, 2004.
[33] Рыбалов А.Н. Сложность вычислений в алгебраических системах // Сибирский математический журнал, Т.45. №6, С. 1365-1377, 2004.
[34] Рыбалов А.Н. Полиномиальные классы сложности по пространству над полем действительных чисел // Вестник Омского университета, М, С. 19-21, 2004.
[35] Рыбалов А.Н. NP-неполные проблемы над полем действительных чисел // Вестник Омского университета, №3, С. 48-50, 2004.
[36] Рыбалов АН., Релятивизации вопроса P=NP над полем комплексных чисел // Сибирские электронные математические известия, Т. 1, С. 91-98, 2004.
Рыбалов Александр Николаевич
Сложность вычислений в алгебраических системах
Специальность 01.01.06 - математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Подписано в печать 24.11.04. Формат бумаги 60x84 1/16. Печ. л. 1,25. Уч.-изд. л. 1,25. Тираж 100 экз. Заказ №606
Издателъско-полиграфический отдел ОмГУ 644077, г. Омск-77, пр. Мира 55-а.
№25090
Введение
1. Предварительные сведения
1.1. Классическая теория сложности вычислений.
1.1.1. Теорема Кука-Левина
1.1.2. Теорема Ладнера
1.1.3. Теорема Бэйкера-Джилла-Соловэя.
1.2. Обобщенная вычислимость.
1.2.1. Вычислимость над списочной надстройкой
1.2.2. 5-вычислимость Хеммерлинга.
2. Сложность вычислений в алгебраических системах
2.1. Основные определения
2.2. Примеры полиномиальных функций
3. Полиномиальная эквивалентность подхода Хеммерлинга и вычислимости над списочной надстройкой
3.1. Моделирование 5-вычислимости
3.2. Моделирование вычислимости над списочной надстройкой
3.3. Моделирование тьюринговой вычислимости.
4. Полные проблемы
4.1. Полные проблемы в классе NP
4.2. Полные проблемы в классе DNP
5. Сложность вычислений в некоторых классических алгебраических системах
5.1. Характеристики вычислительных путей.
5.2. Р ф DNP над кольцом вещественных матриц
5.3. Неупорядоченное поле вещественных чисел
5.3.1. Безусловный аналог теоремы Ладнера
5.3.2. Полиномиальные классы по пространству.
5.4. Р ф DNP над полем С с целочисленным оракулом . 87 Список литературы
Классическая теория сложности вычислений берет свое начало с середины 20 века, когда появились первые компьютеры. В уже существовавшей к тому времени теории алгоритмов вычислительные процессы рассматривались без ограничения на ресурсы, которые возникают при реализации вычислительных устройств на практике. Главными такими физическими ресурсами являются время выполнения алгоритма и пространство (память), требуемая вычислительному устройству в процессе выполнения алгоритма. В теории сложности под алгоритмом как правило понимается машина Тьюринга (МТ), т.к. эта вычислительная модель очень хорошо отражает свойства реальных компьютеров. Машины Тьюринга могут вычислять функции вида / : £* —»~£* или распознавать множества вида Л С Е*, где £ - некоторый конечный алфавит (обычно £ = {0,1}). Время работы Ьм{х) МТ М на входе х £ £* - это число шагов МТ на входном слове х до ее остановки = если машина не останавливается). Пространство sm(x) машины М на х - это число ячеек ее рабочей ленты, используемых в вычислении.
Любую проблему, решаемую на компьютере, можно при помощи кодирования представить как проблему распознавания некоторого множества А строк подходящего конечного алфавита. С практической точки зрения наиболее важной информацией о множестве А является оценка сверху времени или пространства распознающего А алгоритма в зависимости от размера входных данных. Так как в теории сложности входами алгоритмов являются строки, то естественный размер входа - это длина входного слова. Таким образом, возникает понятие сложностного класса по времени:
TIME(f) = {А С £* : существует МТ М, распознающая А такая, что для любого х имеет место < /(М)} и, аналогично, по пространству
SPACE(f) = {А С £* : существует МТ М, распознающая А такая, что для любого х имеет место sm{x) < /(|я|)}, где / : N —> N - некоторая возрастающая функция. Большинство практических алгоритмов имеют полиномиальную оценку времени, поэтому, начиная с работ [19] и [22], выделяют следующие важные классы оо
P=\jTIME{nk + к), к=1 оо
РSPACE = (J SPACE(nk + к). к=1
С 1970-х годов в теории сложности вычислений появляется новая вычислительная модель - недетерминированная машина Тьюринга (НМТ). В НМТ есть так называемые недетерминированные состояния, из которых возможен переход сразу в несколько последующих состояний. На одном и том же входе такая машина может иметь несколько вычислительных путей (т.е. последовательностей состояний, возникающих в процессе работы машины). Таким образом, время и пространство такой машины М на входе х зависят от пути г, по которому происходит вычисление: tM,r{%) и sm,t{x)- Определяются недетерминированные сложностные классы по времени
NTIME(f) = {А С Е* : 3 НМТ М такая, что х € А<&3т принимающий выч. путь М на х такой, что Ьм,т{х) < f{\x\)} и по пространству
NSPACE(f) = {А С £* : 3 НМТ М такая, что х <Е А & Зт принимающий выч. путь М на х такой, что sm,t(x) < /(Несоответствующие полиномиальные классы определяются аналогично детерминированному случаю: оо
NP = (J NTIME{ п' + к), к=1 оо
NP SPACE = |J NSPACE(nk + к). к=1
С момента своего появления эти классы активно изучаются. В 1971 г. С.Кук в статье [20] доказал, что в классе NP существуют полные относительно полиномиальной сводимости множества и привел пример такого множества (проблемы), связанной с выполнимостью булевых формул. В 1972 г. Р.Карп в статье [27] доказал, что многие практически важные комбинаторные проблемы являются NP-полными. Л.Левин в работе [5] независимо от них получил аналогичные результаты в его терминах так называемых универсальных переборных задач. В 1972 г. У.Сэвич в работе [36] показал, что PSPACE = NPSPACE. В 1975 г. Р.Ладнер в работе [29] доказал, что при условии истинности Р ф NP, в NP \ Р существуют множества, не являющиеся полными относительно полиномиальной сводимости. В 1975 г. Бэйкер, Джилл и Соловэй в [13] привели пример оракулов А и В таких, что РА = NPA, но Рв ф NPB. Но, несмотря на многочисленные усилия, вопрос о совпадении классов Р и NP до сих пор остается нерешенным.
С 1980-х годов активно развивается обобщенная вычислимость, обобщающая классическую теорию алгоритмов на произвольную алгебраическую систему 21 = (А, а). Если в этой теории в качестве системы Я1 взять систему с конечным основным множеством А (например, бинарное поле GF(2)), то получится классическая тьюрингова вычислимость.
Можно выделить два основных подхода к построению такой теории: формульный и машинный. В формульном подходе вычислимые функции, предикаты и множества определяются при помощи специальных формул некоторого расширения сигнатуры и. Например, в Е-определимости (Ю.Л.Ершов [4], Дж. Барвайс [14]) вводится семейство наследственно конечных множеств
HF0(A) = А, HFn+l(A) = Vu(HFn(A)), оо
HF(A) = [jHFn(A), п=О где VU(M) — семейство всех конечных множеств с элементами из М. Далее вводится алгебраическая система HF($l) = (HF(A),ai) с сигнатурой <7i =<t(J{0,€2}, где 0 — константный символ, интерпретируемый как пустое множество, а б2 — предикатный символ, интерпретируемый как предикат принадлежности. Класс Е-формул строится из атомарных формул сигнатуры а\ при помощи логических связок, навешивания квантора существования и так называемых ограниченных кванторов Ух € t и Зх £ t, где t - терм сигнатуры (Ji. Теперь функция / : HF(A)k —HF(A) - Е-функция (вычислимая в данном подходе), если ее график определим некоторой Е-формулой.
В машинном подходе вычислимые объекты определяются при помощи некоторых абстрактных вычислительных устройств, которые могут использовать в вычислениях функции, предикаты и константы сигнатуры о или некоторого ее расширения. Так, в 5-вычислимости Хеммерлинга ([26]) — это так называемые /S-машины, в подходе Ашаева, Беляева и Мясникова ([1]) — это машины с неограниченными регистрами (МНР).
-вычислимость была предложена Хеммерлингом в работе [26] и является непосредственным обобщением подхода Блюм, Шуба и Смейла ([18]) к вычислимости над кольцами и полями. Вычислимые функции определяются при помощи 5-машин, которые работают с непустыми строками элементов из основного множества А. Эти вычислительные устройства являются обобщением машины Тьюринга и состоят из рабочей строки, программы и конечного набора указателей на элементы рабочей строки. Инструкции программы позво- -ляют записывать в элемент строки, на который указывает указатель значения функций и констант сигнатуры сг, совершать условные переходы, зависящие от истинности предикатов сигнатуры сг, а также позволяют сдвигать указатели, добавлять и удалять элементы в рабочую строку, ^-машины могут вычислять функции вида / : Л+ —> А+, где А+ - множество всех непустых конечных строк с элементами из А.
Вычислимость над списочной надстройкой была предложена Аш-аевым, Беляевым и Мясниковым в 1993 году в работе [1]. В этом подходе используется введенная в работе [3] списочная надстройка HL(A) основного множества А:
Lо = A, Ln+1 = L(Ln) U L„, оо
HL(A)=\jLn(A),
71=0 где L{M) - множество всех конечных списков с элементами из М. Далее расширяется сигнатура а до сигнатуры а* добавлением функций для работы со списками: cons - добавление одного списка в конец другого, tail - отбрасывание первого элемента списка, head - взятие первого элемента списка, а также добавлением константы nil, интерпретируемой как пустой список. В итоге получается система HL($l) = (HL(A),cг*), которая называется списочной надстройкой системы 21. Вычислимые функции вида / : HL(A) —> HL(A) определяются при помощи машин с неограниченными регистрами (МНР), которые в своих командах используют функции, предикаты и константы сигнатуры а*.
Общей чертой всех этих подходов является введение некоторой дискретной структуры над основным множеством, позволяющей получать вспомогательные конструкции из элементов А, необходимые для развития теории вычислимости в системе 21. Для Е-определимос-ти - это наследственно конечные множества HF(A), для ^-вычисли-мости - это строки элементов из А, для вычислимости над списочной надстройкой - это списочная надстройка HL(A). Более того, в некотором смысле эти подходы являются эквивалентными. В работе [7] показано, что 5-вычислимость и вычислимость над списочной надстройкой, ограниченная на списки Ь\(А), приводят к одному и тому же классу вычислимых функций вида / : А+ А+ (строки элементов из А можно отождествлять с L\(A) - списками глубины 1 из элементов А). В работе [8] доказана эквивалентность S-определимости и подхода Московакиса ([32]), а также эквивалентность вычислимости над списочной надстройкой и подхода Московакиса в случае примитивно-рекурсивных функций.
Теория сложности вычислений над произвольными алгебраическими системами берет свое начало с работы Блюм, Шуба и Смейла [18], в которой она была развита на основе теории вычислимости над кольцами и полями. Отметим основные моменты этого подф хода. Пусть R = (А, {+, —, х, С а}) - некоторое кольцо, где С а ~ все элементы множества А, добавленные в качестве констант и интерпретируемые сами собой. Входами, с которыми работают вычислительные устройства, являются строки элементов из R. Под размером строки понимается ее длина - таким образом при этом происходит отвлечение от природы элементов множества А, которая может быть неконструктивной (например, комплексные и вещественные числа), а внимание сосредотачивается на дискретных структурах (строках, списках и т.д.). Абстрактное вычислительное устройство (BSS-машина) - это 5-машина для алгебраической системы R. Время работы такой машины - число инструкций, выполненных от начала работы до ее остановки. В частности, операции с элементами кольца происходят за единицу времени - опять игнорируется природа элементов кольца. Класс Р над R состоит из множеств строк, распознаваемых .ВЗ^-машинами за полиномиальное время. Недетерминированные BSS-машины допускают так называемые инструкции подсказки, которые присваивают элемен-* ту рабочей строки произвольный элемент из А. После выполнения такой инструкции, машина имеет более одного варианта дальнейшей работы. С помощью недетерминированных £55-машин дается определение класса NP, аналогичное классическому. Позже в работе [21] был определен класс DNP аналогично классу NP, но с помощью более узкого класса недетерминированных BSS-малшя, в которых вместо инструкций подсказки используются недетерминированные переходы - команды перехода сразу к двум последующим инструкциям. Для колец с более чем одним элементом в А недетерминированные переходы можно смоделировать инструкциями подсказки, а потому для таких систем имеет место включение DNP С NP. Другие определения классической теории сложности вычислений подобным образом переносятся на кольцо R. В случае, когда кольцо R конечно, получается классическая теория вычислительной сложности над строками из конечного алфавита. Основной упор в работе [18] делается на поле комплексных чисел С и упорядоченное поле действительных чисел R. В случае комплексных чисел, например, приведен следующий пример iVP-полного множества:
HN = {code(fu .,/„): ЗхвСк fx(x) = 0. fn(x) = 0}, где code - некоторая кодировка полиномов с комплексными коэффициентами строками комплексных чисел. Были также поставлены вопросы о совпадении классов Р и NP над полями С и Е, первому из которых посвящена работа [17]. В дальнейшем подход Блюм, Шуба и Смейла был обобщен Хеммерлингом на произвольную алгебраическую систему в работе [26].
Некоторые из результатов классической теории сложности вычислений были перенесены на поля С, IR и произвольные алгебраические системы. Прежде всего, это теорема Кука-Левина о существовании iVF-полных проблем, перенесенная Блюм, Шубом и Смейлом на поле С, и Хеммерлингом на некоторые типы алгебраических систем в статье [26]. Так же можно отметить результат Меера и Ма-лаховича в [30], переносящий теорему Ладнера на поле С, а также работу Бен-Давида, Меера и Мишо [15], в которой доказано, что теорема Ладнера при некоторых дополнительных условиях имеет место над полем М с порядком. Эмерсон в работе [23] переносит классическую теорему Бэйкера-Джилла-Соловэя на упорядоченное поле Ш.
Много исследований было посвящено аналогам проблемы Р = NP1 в различных алгебраических системах. Меер в 1992 г. в pall боте [31] доказал, что Р ф NP над аддитивной группой действительных чисел (фактически он доказал, что Р ф DNP). В дальнейшем Койран в [28] упростил доказательство этого факта. Гасснер в 2002 г. в статье [25] дала доказательство неравенства Р ф DNP для всех бесконечных абелевых групп. Прунеску в [33] упростил его. Пойзат показал, что для бесконечных алгебраически незамкнутых полей имеет место Р ф NP (этот результат опубликован в монографии [16] в 1996 г.). В частности, из этого следует, что Р ф NP для неупорядоченного поля действительных чисел. Прунеску в 2003 г. в статье [34] доказал неравенство Р ф DNP для бесконечных булевых алгебр. В 2004 г. в работе [35] автором было доказано, что Р ф DNP для кольца вещественных матриц с константами: нулевой и единичной матрицей. Проблема Р = DNP? для полей СиЕ,а также проблема Р = NP1 для поля С и упорядоченного поля М. до сих пор нерешены. В работе [17] установлены связи между истинностью неравенства Р ф NP над С и некоторыми теоретико-числовыми гипотезами. Так же можно отметить работу [24], в которой показано, что Р ф NP над упорядоченной аддитивной группой действительных чисел тогда и только тогда, когда Р ф NP в классической теории.
Основной целью нашего исследования является развитие нового подхода к сложности вычислений в произвольной алгебраической системе на основе вычислимости над списочной надстройкой, предложенной Ашаевым, Беляевым и Мясниковым в [1]. В частности, обобщение классической теоремы Кука-Левина о существовании NP-полных множеств. Сравнение нашего подхода с подходом Хеммер-линга на строках и моделирование классической тьюринговой теории сложности вычислений. Также нас интересуют проблемы типа
Р = iVP? и истинность некоторых классических фактов в конкретных алгебраических системах (в полях СиЕ, матричных кольцах и т.д.).
В работе используются и развиваются методы теории алгоритмов и теории сложности вычислений, логики и алгебры.
Все результаты диссертации, выносимые на защиту, являются новыми. Они получены автором самостоятельно и опубликованы в пяти журнальных статьях [9, 10, 11, 12, 35].
Работа имеет теоретическое значение. Получено обобщение теоремы Кука-Левина в рамках нового подхода к вычислительной сложности в алгебраических системах. Исследована проблема Р = NP7 над кольцом вещественных матриц и ее релятивизованная версия над полем С.
Результаты диссертации могут быть использованы при чтении спецкурсов по теории алгоритмов и вычислительной сложности, при подготовке учебных пособий.
Основные результаты для диссертации опубликованы в пяти научных статьях [9, 10, 11, 12, 35], были доложены на алгебраическом семинаре в Омском госуниверситете, а также на Международной конференции "Мальцевские чтения" (Новосибирск, 2003, 2004) и Международной конференции "Алгебра, логика и кибернетика" (Иркутск, 2004).
Диссертация изложена на 95 страницах, состоит из введения, пяти глав и списка литературы. Главы разбиты на параграфы.
1. Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика, Т.32, №4, С. 349-386, 1993.
2. Вялый М., Китаев А., Шень А. Классические и квантовые вычисления. М.:МЦНМО, ЧеРо, 1999.
3. Гончаров С.С., Свириденко Д.И. Е-программирование. Логико-математические проблемы МОЗ (Вычислительные системы, вып. 107), Новосибирск, С. 3-29, 1985.
4. Ершов Ю.Л. Определимость и вычислимость. Новосибирск: Научная книга, 1996.
5. Левин Л. Универсальные переборные проблемы // Проблемы передачи информации, 9(3), С. 265-266, 1973.
6. Романов Р.В. Некоторые проблемы обобщенной вычислимости. Препринт №98-03, С.1-32, Омск, 1998.
7. Рыбалов А.Н. Два подхода к обобщенной вычислимости на строках. Препринт №2000-02, С. 1-26, Омск, 2000.
8. Рыбалов А.Н. Три подхода к обобщенной вычислимости. Препринт №01-03, С. 1-28, Омск, 2001.
9. Рыбалов А.Н. Сложность вычислений в алгебраических системах // Сибирский математический журнал, Т.45, №6, С. 1365— 1377, 2004.
10. Рыбалов А.Н. Полиномиальные классы сложности по пространству над полем действительных чисел // Вестник Омского университета, №1, С. 19-21, 2004.
11. Рыбалов А.Н. NP-неполные проблемы над полем действительных чисел // Вестник Омского университета, №3, С. 48-50, 2004.
12. Рыбалов А.Н., Релятивизации вопроса P=NP над полем комплексных чисел // Сибирские электронные математические известия, Т. 1, С. 91-98, 2004.
13. Baker Т., Gill J., Solovay R. Relativizations of the P=?NP question // SIAM Journal on Computing, 4, pp. 431-442, 1975.
14. Barwise J. Admissible sets and structures. Springer, 1975.
15. Ben-David S., Meer K., Michaux C. A note on non-complete problems in NPr // Journal of Complexity, vol. 16, №1, pp. 324-332, 2000.
16. Blum L., Cucker F., Shub M., Smale S. Complexity and Real Computation. Springer, 1998.
17. Blum L., Cucker F., Shub M., Smale S. Algebraic Settings for the Problem "P=NP" // Lectures in Applied Mathematics, vol 32, pp. 125-144, Amer. Math. Soc. 1996.
18. Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines // Bull. Amer. Math. Soc., 21, pp. 1-46, 1989.
19. Cobham A. The intrinsic computational difficulty of functions. // Proceedings of the 1964 Internationnal Congress for Logic, Metodol-ogy and Philosophy of Science, pp. 24-30. Elsevier/North-Holland, 1964.
20. Cook S. The complexity of theorem-proving procedures // Proceedings of 3d Annual ACM Symposium on Theory of Computing, pp. 151-158, 1971.
21. Cucker F., Matamala M. On digital nondeterminism // Math. Syst. Theory, 29, pp. 635-647, 1996.
22. Edmonds J. Minimum partion of a matroid into independent subsets. // J. Res. Nat. Bur. Standarts Sect. B, 69, pp. 67-72, 1965.
23. Emerson T. Relativization of the P=?NP question over the reals (and other ordered rings) // Theoretical Computer Science 133, pp. 15-22, 1994.
24. Fournier H., Koiran P. Are lower bounds easier over the reals? // Proc. 30th ACM Symposium on Theory of Computing, pp. 507-513, 1998.
25. Gafiner C. The P — DNP problem for infinite abelian groups // Journal of Complexity, 17, pp. 574-583, 2001.
26. Hemmerling A. Computability and complexity over structures // Math. Logic Quarterly, 44, No.l, pp. 1-44, 1998.
27. Karp R. Reducibility among combinatorial problems // Complexity of Computer Computations, pp. 85-103, NY, 1972.
28. Koiran P. Computing over the reals with addition and order // Theoretical Computer Science, 133, pp. 35-47, 1994.
29. Ladner R. On the structure of polynomial time reducibility // Journal of the ACM, vol. 22, pp. 155-171, 1975.
30. Malajovich G., Meer K. On the structure of NPC // SIAM Journal on Computing, vol. 28, №1, pp. 27-35, 1999.
31. Meer K. A note on P ф NP result for a restricted class of real machines // Journal of Complexity, 8, pp. 451-453, 1992.
32. Moschovakis Y.N. Abstract first order computability // Trans. Amer. Math. Soc., vol. 138, pp. 427-464, 1969.
33. Prunescu M. A model-theoretic proof for P ф NP over all infinite abelian groups // Journal of Symbolic Logic, Vol. 67, №.1, pp. 235238, 2002.
34. Prunescu M. P Ф NP for all infinite Boolean algebras // Math. Logic Quarterly, 49, №.2, pp. 210-213, 2003.
35. Rybalov A. On the P-NP problem over real matrix rings // Theoretical Computer Science, Vol. 314/1-2, pp. 281-285, 2004.
36. Savitch W. Relationships between nondeterministic and deterministic tape complexities // Journal of Computer and System Sciences, 4(2), pp. 177-192, 1970.
