Введение к работе
Актуальность темы. Классическая теория сложности вычислений берет свое начало с середины 20 века, когда появились первые компьютеры. В уже существовавшей к тому времени теории алгоритмов вычислительные процессы рассматривались без ограничения на ресурсы, которые возникают при реализации вычислительных устройств на практике. Главными такими физическими ресурсами являются время выполнения алгоритма и пространство (память), требуемая вычислительному устройству в процессе выполнения алгоритма. В теории сложности под алгоритмом как правило понимается машина Тьюринга (МТ), т.к. эта вычислительная модель очень хорошо отражает свойства реальных компьютеров. Машины Тьюринга могут вычислять функции вида / : Е* —> * или распознавать множества вида А С Е% где Е -некоторый конечный алфавит (обычно Е = {0,1}). Время работы tM (х) МТ М на входе х * - это число шагов МТ на входном слове /до ее остановки (д/(х) = оо, если машина не останавливается). Пространство Зм(х) машины М н ж - это число ячеек ее рабочей ленты, используемых в вычислении.
Любую проблему, решаемую на компьютере, можно при помощи кодирования представить как проблему распознавания некоторого множества А строк подходящего конечного алфавита. С практической точки зрения наиболее важной информацией о множестве А является оценка сверху времени или пространства распознающего А алгоритма в зависимости от размера входных данных. Так как в теории сложности входами алгоритмов являются строки, то естественный размер входа - это длина входного слова. Таким образом, возникает понятие сложностного класса по времени:
TIME(f) = {А С Е* : существует МТ М, распознающая А
такая, что для любого х имеет место tut (і) < /(|я|)} и, аналогично, по пространству
SPACE(f) — {А С Е* : существует МТ М, распознающая А
такая, что для любого % имеет место вц(х) < /(|i|)}>
где / : N —> N - некоторая возрастающая функция. Большинство практических алгоритмов имеют полиномиальную оценку времени, поэтому, начиная с работ [15] и [18], выделяют следующие важные классы
Р=[]Т1МЕ{пк + к),
*=1
PSPACE = [J SPACE(nk + it).
С 1970-х годов в теории сложности вычислений появляется новая вычислительная модель - недетерминированная машина Тьюринга (НМТ). В НМТ есть так называемые недетерминированные состояния, из которых возможен переход сразу в несколько последующих состояний. На одном и том же входе такая машина может иметь несколько вычислительных путей (т.е. последовательностей состояний, возникающих в процессе работы машины). Таким образом, время и пространство такой машины М на входе X зависят от пути да, по которому происходит вычисление: (м,т(х) ияд/,т(х). Определяются недетерминированные еложностные классы по времени
NTIME(f) = {А С ': 3 НМТ М такая, что х А « Зт -
принимающий выч. путь Мна х такой, что t\[>r(x) < /(|х|)} и по пространству NSPACE{f) = {А С Е*: 3 НМТ М такая, что х Є А & Эг -„
принимающий выч. путь Мна х такой, что Sm,t{x) < /(Несоответствующие полиномиальные классы определяются аналогично детерминированному случаю:
NP = \jNTIME(nk + k),
NPSPACE = [] NSPACE(nk + к). і=і
С момента своего появления эти классы активно изучаются. В 1971 г. С.Кук в статье [16] доказал, что в классе NP существуют полные относительно полиномиальной сводимости множества
-.. **f A'1
и привел пример такого множества (проблемы), связанной с выполнимостью булевых формул. В 1972 г. Р. Карп в статье [23] доказал, что многие практически важные комбинаторные проблемы являются iVP-полными. ЛЛевин в работе [5] независимо от них получил аналогичные результаты в его терминах так называемых универсальных переборных задач. В 1972 г. У.Сэвич в работе [31] показал, что PSPACE = NPSPACE. В 1975 г. Р.Ладнер в работе [25] доказал, что при условии истинности Р ф NP, В NP\P существуют множества, не являющиеся полными относительно полиномиальной сводимости. В 1975 г. Бэйкер, Джилл и Соловэй в [9] привели пример оракулов А и В таких, что РА = NPA, но Р ф NP . Но, несмотря на многочисленные усилия, вопрос о совпадении классов Р и NP до сих пор остается нерешенным.
С 1980-х годов активно развивается обобщенная вычислимость, обобщающая классическую теорию алгоритмов на произвольную алгебраическую систему 21 = {А, а). Если в этой теории в качестве системы 2t взять систему с конечным основным множеством А (например, бинарное поле GF(2)), то получится классическая тьюрингова вычислимость.
Можно выделить два основных подхода к построению такой теории: формульный и машинный. В формульном подходе вычислимые функции, предикаты и множества определяются при помощи специальных формул некоторого расширения сигнатуры а. Например,в Е-определимости (Ю.Л.Ершов [4], Дж. Барвайс [10]) вводится семейство наследственно конечных множеств
HF0(A) = А, НРШ(А) = K(HFn{A}),
HF(A) - (J HFa(A),
п=0
где ~РШ{М) — семейство всех конечных множеств с элементами из М. Далее вводится алгебраическая система НР(Щ = (HF{A),0\) с сигнатурой <Т\ = a U {0, Є2}, где 0 — константный символ, интерпретируемый как пустое множество, а Є2 — предикатный символ, интерпретируемый как предикат принадлежности. Класс Е-формул строится из атомарных формул сигнатуры 0\ при помощи логических связок, навешивания квантора существования и так называемых ограниченных кванторов Vx Є t И Зх Є t, где t - терм сигнатуры о\. Теперь функция / : HF{A)k -> HF{A) -
2-функция (вычислимая в данном подходе), если ее график определим некоторой 2-формулой.
В машинном подходе вычислимые объекты определяются при помогли некоторых абстрактных вычислительных устройств, которые могут использовать в вычислениях функции, предикаты и константы сигнатуры а или некоторого ее расширения. Так, в S-вычислимости Хеммерлинга ([22]) — это так называемые S-машины, в подходе Ашаева, Беляева и Мясникова ([1]) — это машины с неограниченными регистрами (МНР).
5-вычислимость была предложена Хеммерлингом в работе [22] и является непосредственным обобщением подхода Блюм, Шуба и Смейла ([14]) к вычислимости над кольцами и полями. Вычислимые функции определяются при помощи 5-машин, которые работают с непустыми строками элементов из основного множества А. Эти вычислительные устройства являются обобщением машины Тьюринга и состоят из рабочей строки, программы и конечного набора указателей на элементы рабочей строки. Инструкции программы позволяют записывать в элемент строки, на который указывает указатель значения функций и констант сигнатуры а, совершать условные переходы, зависящие от истинности предикатов сигнатуры а, а также позволяют сдвигать указатели, добавлять и удалять элементы в рабочую строку. S-машины могут вычислять функции вида / : А+ -+ А+, где А+ - множество всех непустых конечных строк с элементами из А.
Вычислимость над списочной надстройкой была предложена Алиевым, Беляевым и Мясниковым в 1993 году в работе [1]. В этом подходе используется введенная в работе [3] списочная надстройка HL{A) основного множества А:
Lq = A, L„H = L(L„)l)Ln, ЯЦА) = (J А.И),
71=0
где L(M) - множество всех конечных списков с элементами из М. Далее расширяется сигнатура а до сигнатуры <т* добавлением функций для работы со списками: cons - добавление одного списка в конец другого, tail - отбрасывание первого элемента списка, head - взятие первого элемента списка, а также добавлением константы nil, интерпретируемой как пустой список. В
итоге получается система HL(Ql) = (HL{A), а*), которая называется списочной надстройкой системы 21. Вычислимые функции вида / : HL(A) —» HL(A) определяются при помощи машин с неограниченными регистрами (МНР), которые в своих командах используют функции, предикаты и константы сигнатуры а*.
Общей чертой всех этих подходов является введение некоторой дискретной структуры над основным множеством, позволяющей получать вспомогательные конструкции из элементов А, необходимые для развития теории вычислимости в системе 21. Для 2-определимости - это наследственно конечные множества HF(A), для 5-вычислимости - это строки элементов из А, для вычислимости над списочной надстройкой - это списочная надстройка HL(A). Более того, в некотором смысле эти подходы являются эквивалентными. В работе [7] показано, что 5-вычислимость и вычислимость над списочной надстройкой, ограниченная на списки L\{A), приводят к одному и тому же классу вычислимых функций вида / : А+ —» Л+ (строки элементов из А можно отождествлять с 1ц(А) - списками глубины 1 из элементов А). В работе [8] доказана эквивалентность 2-определимости и подхода Моско-вакиса ([28]), а также эквивалентность вычислимости над списочной надстройкой и подхода Московакиса в случае примитивно-рекурсивных функций.
Теория сложности вычислений над произвольными алгебраическими системами берет свое начало с работы Блюм, Шуба и Смейла [14], в которой она была развита на основе теории вычислимости над кольцами и полями. Отметим основные моменты этого подхода. Пусть R — (А, {+, —, Х,Сд}) - некоторое кольцо, где С а - все элементы множества А, добавленные в качестве констант и интерпретируемые сами собой. Входами, с которыми работают вычислительные устройства, являются строки элементов из R. Под размером строки понимается ее длина - таким образом при этом происходит отвлечение от природы элементов множества А, которая может быть неконструктивной (например, комплексные и вещественные числа), а внимание сосредотачивается на дискретных структурах (строках, списках и т.д.). Абстрактное вычислительное устройство (BSS-машина) - это 5-машина для алгебраической системы R. Время работы такой машины -число инструкций, выполненных от начала работы до ее остановки. В частности, операции с элементами кольца происходят за
единицу времени - опять игнорируется природа элементов кольца. Класс Р над R состоит из множеств строк, распознаваемых BSS-малшнами за полиномиальное время. Недетерминированные BSS-машяны допускают так называемые инструкции подсказки, которые присваивают элементу рабочей строки произвольный элемент из А. После выполнения такой инструкции, машина имеет более одного варианта дальнейшей работы. С помощью недетерминированных BSS-машин дается определение клас N
HIf = {code{fil... ,Д): Зх С* /i(i) = 0.../..(*) =0},
где code - некоторая кодировка полиномов с комплексными коэффициентами строками комплексных чисел. Были также поставлены вопросы о совпадении классов Р и NP над полями С и R, первому из которых посвящена работа [13]. В дальнейшем подход Блюм, Шуба и Смейла бьш обобщен Хеммерлингом на произвольную алгебраическую систему в работе [22].
Некоторые из результатов классической теории сложности вычислений были перенесены на поля С, Ш. и произвольные алгебраические системы. Прежде всего, это теорема Кука-Левина о существовании iVP-полных проблем, перенесенная Блюм, Шубом и Смейлом на поле С, и Хеммерлингом на некоторые типы алгебраических систем в статье [22]. Так же можно отметить результат Меера и Малаховича в [26], переносящий теорему Ладнера на поле С, а также работу Бен-Давида, Меера и Милю [И], в которой
доказано, что теорема Ладнера при некоторых дополнительных условиях имеет место над полем К с порядком. Эмерсон в работе [19] переносит классическую теорему Бэйкера-Джилла-Соловэя на упорядоченное поле R.
Много исследований было посвящено аналогам проблемы Р — NP1 в различных алгебраических системах. Меер в 1992 г. в работе [27] доказал, что Р ф NP над аддитивной группой действительных чисел (фактически он доказал, что Р ф DNP). В дальнейшем Койран в [24] упростил доказательство этого факта. Гасснер в 2002 г. в статье [21] дала доказательство неравенства Р ф DNP для всех бесконечных абелевых групп. Прунеску в [29] упростил его. Пойзат показал, что для бесконечных алгебраически незамкнутых полей имеет место Р ф NP (этот результат опубликован в монографии [12] в 1996 г.). В частности, из этого следует, что Р ф NP для неупорядоченного поля действительных чисел. Прунеску в 2003 г. в статье [30] доказал неравенство Р ф DNP для бесконечных булевых алгебр. В 2004 г. в работе [32] автором было доказано, что Р ф DNP для кольца вещественных матриц с константами: нулевой и единичной матрицей. Проблема Р = DNP1 для полей С и 1, а также проблема Р = NP1 для поля С и упорядоченного поля R. до сих пор нерешены. В работе [13] установлены связи между истинностью неравенства Р ф NP над С и некоторыми теоретико-числовыми гипотезами. Так же можно отметить работу [20], в которой показано, что Р ф NP над упорядоченной аддитивной группой действительных чисел тогда и только тогда, когда Р ф NP в классической теории.
. Цель работы. Основной целью нашего исследования является развитие нового подхода к сложности вычислений в произвольной алгебраической системе на основе вычислимости над списочной надстройкой, предложенной Ашаевым, Беляевым и Мясниковым в [1]. В частности, обобщение классической теоремы Кука-Левина о существовании ЛУ-полных множеств. Сравнение нашего подхода с подходом Хеммерлинга на строках и моделирование классической тьюринговой теории сложности вычислений. Также нас интересуют проблемы типа Р = NP7 и истинность некоторых классических фактов в конкретных алгебраических системах (в полях С и R, матричных кольцах).
Методы исследования. В работе используются и развиваются методы теории алгоритмов и теории сложности вычислений,
логики и алгебры.
Теоретическая значимость. Работа имеет теоретическое
значение. Получено обобщение теоремы Кука-Левина в рамках нового подхода к вычислительной сложности в алгебраических системах. Исследована проблема Р = NP? над кольцом вещественных матриц и ее релятивизованная версия над полем С.
Практическая ценность. Результаты данной диссертации могут быть использованы при чтении спецкурсов по теории алгоритмов и вычислительной сложности, при подготовке учебных пособий.
Апробация работы и публикации. Основные результаты для диссертации опубликованы в работах [32, 33, 34, 35, 36], бьши доложены на алгебраическом семинаре в Омском госуниверситете, а также на Международной конференции "Мальцевские чтения" (Новосибирск, 2003, 2004) и Международной конференции "Алгебра, логика и кибернетика" (Иркутск, 2004).
Структура и объем работы. Диссертация изложена на 95 страницах, состоит из введения, пяти глав и списка литературы. Главы разбиты на параграфы.
