Сложность вычислений в алгебраических системах

• Автор: Рыбалов, Александр Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Омск
• Количество страниц: 95 с.

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. Полные проблемы в классе 75ЛТР

5. Сложность вычислений в некоторых классических алгебраических системах
5.1. Характеристики вычислительных путей
5.2. Р ф ИЫР над кольцом вещественных матриц
5.3. Неупорядоченное поле вещественных чисел
5.3.1. Безусловный аналог теоремы Ладнера
5.3.2. Полиномиальные классы по пространству
5.4. Р ф DNP над полем С с целочисленным оракулом
Список литературы

Классическая теория сложности вычислений берет свое начало с середины 20 века, когда появились первые компьютеры. В уже существовавшей к тому времени теории алгоритмов вычислительные процессы рассматривались без ограничения на ресурсы, которые возникают при реализации вычислительных устройств на практике. Главными такими физическими ресурсами являются время выполнения алгоритма и пространство (память), требуемая вычислительному устройству в процессе выполнения алгоритма. В теории сложности под алгоритмом как правило понимается машина Тьюринга (МТ), т.к. эта вычислительная модель очень хорошо отражает свойства реальных компьютеров. Машины Тьюринга могут вычислять функции вида / : Е* —>'Е* или распознавать множества вида А С Е*, где Е - некоторый конечный алфавит (обычно Е = {0,1}). Время работы £м(аО МТ М на входе х £ Е* - это число шагов МТ на входном слове х до ее остановки (Ьм{х) = оо, если машина не останавливается). Пространство йм(^) машины М на т - это число ячеек ее рабочей ленты, используемых в вычислении.
Любую проблему, решаемую на компьютере, можно при помощи кодирования представить как проблему распознавания некоторого множества А строк подходящего конечного алфавита. С практической точки зрения наиболее важной информацией о множестве А является оценка сверху времени или пространства распознающего А алгоритма в зависимости от размера входных данных. Так как в теории сложности входами алгоритмов являются строки, то естественный размер входа - это длина входного слова. Таким образом,
сколько сложнее.
N + М + 3 •— п и
N + М + 4 Rk+з • “
N + М + 5 if Rk+3 = nil goto N + M +
N + M + 6 Rk+2 cons{Rk+2, heacl(R0))
N + M + 7 R0:=tail(R0)
N + M + 8 Rk+з := tail(Rk+i)
N + M + 9 goto IV+ M 4
N + M + 10 if i?i = Rk+i goto iV 4- M +
N + M + 11 goto N -f- M
N + M4-12 R := Дх
N + M + 7 4- 3k if Rk = 7?&+i goto IV 4- M + 9 + ЗА;
N + M + 8 + 3k goto N + M + 10 + 3k
N + M + 9 + 3k Rk := Rk
N + M + 10 + 3k Rk+l -.= Rk+1
N + M+ 11 +3k R0 :=Rk+1Команды с N + M + 3-й по IV + М + 9-ю записывают в Rk+2 новую рабочую строку. Далее корректируются указатели и новая длина рабочей строки Rk+i. Время выполнения этого блока - 0(^(x)2), из-за операций с временной сложностью 0(ім(х)) в цикле длиной 0(£м(#))- Итого, моделирование инструкции удаления имеет сложность 0(ім{х)2)-