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

Содержание
Введение
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. Полные проблемы в классе АГР
4.2. Полные проблемы в классе ИМР
5. Сложность вычислений в некоторых классических алгебраических системах .
5.1. Характеристики вычислительных путей
5.2. Р ф ЛГР над кольцом вещественных матриц
5.3. Неупорядоченное поле вещественных чисел
5.3.1. Безусловный аналог теоремы Ладнера .
5.3.2. Полиномиальные классы по пространству.
5.4. Р ф ИМР над полем С с целочисленным оракулом .
Список литературы