6 Неразрешимые задачи
1? – означает: выполняется ли равенство NP-time = P-time или нет. Ответ на этот вопрос неизвестен и стоит $1000000.
2? – означает: выполняется ли равенство NP-space= Np-time или нет (то есть существуют ли задачи, которым хватает полиномиальной памяти, но за полиномиальное время даже на НДМТ их решить нельзя). Ответ на этот вопрос так же неизвестен.
3?- означает: существуют ли задачи, которые нельзя решить, используя только полиномиальную память. Ответ на этот вопрос дается
Теоремой 5.10
Существует задача( задача непустоты дополнения полурасширенного выражения), которая решаема. Но для ее решения требуется больше чем
памяти, где - константа, сколь угодно большая. Тем более эта задача не решаема за полиномиальное время с использованием полиномиальной памяти.
Без доказательства.
4? – означает: существуют ли неразрешаемые задачи? Ответ на данный вопрос дается в Разделе 6.
- Основные понятия. Справочный материал
- Основные понятия
- 1.2. Справочный материал. Сравнение скорости роста основных функций
- 2 Новые быстрые версии старых алгоритмов
- 2.1. Сортировки массивов
- 2.1.1 Метод прямого выбора (SelectSort)
- 2.1.2 Быстрая сортировка методом двоичных вставок (MergeSort)
- 2.2. Преобразование Фурье (бпф)
- 2.2.1. Дискретное преобразование Фурье
- 2.2.2. Полубыстрое преобразование Фурье (ппф)
- 2.2.3. Быстрое преобразование Фурье (бпф)
- 2.3. Быстрая свертка
- 2.3.1. Понятие свертки
- 2.3.2. Обычный и быстрый алгоритм свертки
- 2.4. Быстрое умножение
- 2.4.1. Быстрое умножение чисел
- 1 Суммирование
- 4 Произведения чисел вдвое меньшей
- 2.4.2. Быстрое умножение матриц
- 2.4.3. Очень быстрое умножение числе (алгоритм Шенхаге – Штрассена)
- 3. Задачи на графах
- 3.1. Справочный материал
- 3.2. Поиск минимального остова в связном неориентированном взвешенном графе
- 3.3. Нахождение кратчайшего расстояния
- 3.3.1. Алгоритм Форда – Беллмана
- 3.3.2. Алгоритм Дейкстры
- 3.4. Нахождение диаметра, радиуса и центра графа
- 3.5. Задача об изоморфизме графов
- 3.6. Задача коммивояжера. Её решение методом ветвей и границ.
- Задачи динамического программирования
- Задачи динамического программирования. Её решение методом динамического программирования.
- 4.2. Задача об оптимальном наборе самолетом скорости и высоты
- 4.3. Задача грабителя (задача о рюкзаке)
- 4.4. Задача о перемножении матриц
- 5 Классы p и np
- 5.1 Машина Тьюринга
- 5.2 Недетерменированные машины Тьюринга(ндмт)
- 5.3 Сводимость. Np-полнота.
- 5.4 Иерархия по сложности. Труднорешаемые задачи.
- Классы сложности.
- 6 Неразрешимые задачи
- 6.1 Новая модель алгоритма вычислений.
- 6.2 Нумерация программ
- 6.3 Неразрешимые проблемы
- 6.4 Теорема об ускорении
- Лабораторные работы
- Расчетно-графическое задание
- Ответы к домашним заданиям