Сложность вычислений в алгебраических системах тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Рыбалов, Александр Николаевич

• Рыбалов, Александр Николаевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Рыбалов, Александр Николаевич

Введение

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 страницах, состоит из введения, пяти глав и списка литературы. Главы разбиты на параграфы.

Список литературы диссертационного исследования кандидат физико-математических наук Рыбалов, Александр Николаевич, 2004 год

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.