Читать онлайн «Введение в сложность вычислений»

ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ МЕТОДЫ СОВРЕМЕННОЙ МАТЕМАТИКИ Выпуск 2 В. Н. Крупский ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ Москва ФАКТОРИАЛ ПРЕСС 2006 УДК 519. 7 ББК 22. 18 K84 K84 Крупский В. Н. Введение в сложность вычислений/В. Н. Крупский — M. : Факториал Пресс, 2006. — 128 с. — (Методы современной математики; Вып. 2). ISBN 5-88688-083-6 Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности «Защита информации». Излагаются основные идеи и методы теории сложности вычислений. Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов. УДК 519. 7 ББК 22. 18 Серия МЕТОДЫ СОВРЕМЕННОЙ МАТЕМАТИКИ Выпуск 2 Научное издание Владимир Николаевич Крупский ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ Формат 60 х 90/16. Усл. печ. л. 8. Бумага офсетная №1. Гарнитура литературная. Подписано к печати 25. 04. 2006. Тираж 1000 экз. Заказ № 3428. Издательство «Факториал Пресс», 117449, Москва, а/я 331; ЛР ИД № 00316 от 22. 10. 99. ISBN 5-88688-083-6 © Факториал Пресс, 2006. Все права защищены. ОГЛАВЛЕНИЕ I МОДЕЛИ ВЫЧИСЛЕНИЙ 8 Глава 1. Машины Тьюринга 9 §1. Неформальное введение 9 §2. Модели Тьюринга 11 §3. Многоленточные машины Тьюринга 14 Глава 2. Время и память 19 §1. Время и зона машины Тьюринга 19 §2. Цена сокращения алфавита 21 §3. Цена сокращения количества лент 24 Глава 3. Универсальные машины Тьюринга 29 § 1. MT, универсальная для класса С 29 §2. Конструкция универсальной машины . . . . 30 §3. Теоремы об иерархии 33 Глава 4. Моделирование других языков 37 §1. Схема моделирования 37 §2. Моделирование RAM 38 §3. Моделирование булевых схем 41 6 Оглавление II СЛОЖНОСТНЫЕ КЛАССЫ 44 Глава 5. Класс Р 45 §1. Определение класса Р 45 §2. Примеры: целочисленная арифметика . . . . 47 §3. Примеры: арифметика остатков 48 §4. Примеры: сложение и умножение матриц 50 §5. Примеры: связность в графе 52 Глава 6. Класс P/Poly 53 §1. Распознавание языков последовательностями булевых схем 53 §2. Континуальность класса P/Poly 54 §3. Включение Р С P/Poly 55 Глава 7. Класс NP 59 §1. Определение класса NP 59 §2. О проблеме Р ≠ NP 62 §3. Примеры задач класса NP 63 Глава 8. Примеры NP-полных задач 67 §1. Сводимость ^ (Карп), NP-полнота. 67 §2. NP-полнота задачи SAT 69 §3. NP-полнота задачи о клике 71 §4. NP-трудность целочисленного ЛП 72 Глава 9. Класс ВРР 75 §1. Вероятностныевычисления 75 §2. Частотные распознаватели 76 §3. Включение ВРР С P/Poly 79 Глава 10. Распознавание простоты 83 §1. Сведения из теории чисел 83 §2. Извлечение корней 84 §3. Вероятностный алгоритм 84 Оглавление 7 §4. Верификация алгоритма 85 §5. Оценка сложности 88 Глава 11. Конечные игры и класс РН 91 §1. Конечные игры 91 §2.