- •Глава 1
- •§ 1. Затраты алгоритма для данного входа, алгебраическая сложность
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 1. Затраты алгоритма для данного входа
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 2. Асимптотические оценки (формализм)
- •§ 3. Асимптотические оценки (два примера) 23
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 3. Асимптотические оценки (два примера)
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •§ 4. Длина числа как возможный размер входа
- •Глава 2
- •§ 5. Понятие сложности в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 5. Понятие сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства.
- •§ 6. Сортировка и конечные вероятностные пространства 47
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 49
- •Глава 2. Сложность в среднем
- •§ 6. Сортировка и конечные вероятностные пространства 51
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •§ 7. Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем 55
- •Глава 2. Сложность в среднем
- •§ 7. Пример медленного роста сложности в среднем
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •§ 8. Функция затрат рандомизированного алгоритма
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 2. Сложность в среднем
- •Глава 3
- •§ 9. Функции, убывающие по ходу выполнения алгоритма
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 75
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 77
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 79
- •§ 9. Функции, убывающие по ходу выполнения алгоритма 81
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 10. Качество оценок
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимость работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 11. Завершимостъ работы алгоритма
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 12. Вложенные циклы (дополнительные примеры)
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 97
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции
- •§ 13. Нецелые размеры входа и непрерывные оценочные функции 99
- •Глава 4
- •§ 14. Понятие нижней границы сложности
- •§ 14. Понятие нижней границы сложности
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 15. Оптимальные алгоритмы
- •§ 16. Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности
- •§ 16. Асимптотические нижние границы
- •§ 16. Асимптотические нижние границы
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем
- •§ 17. Нижняя граница сложности в среднем 125
- •§ 18. Нижние границы сложности рандомизированных алгоритмов. Принцип Яо
- •§18. Нижние границы сложности рандомизированных алгоритмов 127
- •Глава 5
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 19. Битовые операции
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 20. Наивная арифметика: умножение
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 21. Наивная арифметика: деление с остатком
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 22. Модулярная арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •§ 23. Булева арифметика
- •Глава 5. Битовая сложность
- •Глава 5. Битовая сложность
- •Глава 6
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 24. Простейшие рекуррентные уравнения
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 163
- •§ 25. Об одном классе нелинейных рекуррентных соотношений
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 165
- •§ 25. Об одном классе нелинейных рекуррентных соотношений 167
- •§26. Асимптотические оценки решений рекуррентных неравенств 169
- •§ 26. Асимптотические оценки решений рекуррентных неравенств
- •§ 26. Асимптотические оценки решений рекуррентных неравенств 171
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 173
- •§ 27. Добавление нулей 175
- •§ 27. Добавление нулей
- •§ 27. Добавление нулей 179
- •Глава 7 Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 28. Линейная сводимость
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности
- •§ 29. Линейная сводимость и нижние границы сложности 191
- •Глава 7. Сводимость
- •§ 29. Линейная сводимость и нижние границы сложности 193
- •Глава 7. Сводимость
- •§ 30. Классы PиNp
- •§ 30. Классы р и np
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 30. Классы PuNp
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 201
- •§ 31. Существование задач распознавания, не принадлежащих р. Связь моделей мт и рам
- •Глава 7. Сводимость
- •§ 31. Существование задач распознавания, не принадлежащих р 203
- •Глава 7. Сводимость
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •§ 32. Полиномиальная сводимость. Np-полные задачи
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 7. Сводимость
- •Глава 1. Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае
- •119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-74-83
Глава 7. Сводимость
контекста и определен, по крайней мере, с точностью до полиномиальной сводимости. Обсуждая в дальнейшем задачи из примеров предыдущего параграфа, мы будем иметь в виду рассмотренные там способы кодирования.
Пример 32.2. Покажем сводимость задачи выполнимости КНФ к задаче о клике с указанным числом вершин (пример 30.3). Пусть КНФ F имеет вид (32.1). Построим граф GF с kг + k2 + ... + km вершинами, для которых используем обозначения
lij, i = l,2, ...,m, j = l,2,...,kh
при этом вершины lij и lvw соединяем ребром, если и только если выполнены два условия:
i#v,
конкретные литералы, скрывающиеся в (32.1) за обозначениями lij и lvw, не являются отрицанием друг друга (скажем, если lij—это xъ а lvw— это xъ то эти две вершины ребром не соединяются).
Построение матрицы смежности графа GF может быть выполнено за полиномиально ограниченное время.
Из определения клики и способа построения графа GF следует, что клика из m вершин в этом графе существует, если и только если формула (32.1) выполнима. В самом деле, при наличии такой клики полагаем xs = 0, когда литерал xs соответствует одной из вершин клики, а в остальных случаях xs = l. В результате каждое Di в (32.1) равно 1.
Наоборот, если заданная формула (32.1) выполнима, то при соответствующих значениях всех переменных xъx2, ■■■,xn для каждого i^m можно выбрать j такое, что lij—это литерал со значением 1. Сделав такой выбор, мы получаем набор вершин, образующий клику с m вершинами.
Если исходная КНФ имеет вид
(-x1v-x2)A(x2)A(x1Vx2),
то мы получаем граф GF с пятью вершинами (рис. 25), в котором обнаруживается клика Cln, l2i, l32D с тремя вершинами. Это соответствует тому, что исходная формула принимает значение 1 при xг = 0, x2 = 1.
Задача распознавания существования в графе клики с заданным числом вершин является NP-полной.
г31
а)
б)
.hi
h2*
1и.
207
hi
г32
hi
h2
Рис. 25. Построение графа GF для вершин, б) проведение ребер.
F = xi v *2) л (х2) Л (jq v х2): а) выбор
Доказано также, что задача распознавания гамильтоновости графа является NP-полной1. Упомянем еще одну очень известную NP-пол-ную задачу, называемую задачей о рюкзаке. Задано конечное множество U, размер s(u) gN+ и стоимость v(u) gN+ каждого ue U, а также a, b е N+. Существует ли такое подмножество U' с U, что X! s(") ^ а,
2 v(u)^b? ueU'
ue!7' ?
Из теоремы Кука следует, что для решения проблемы Р = NP достаточно со всей тщательностью рассмотреть какой-нибудь один NP-пол-ный предикат, например, тот же предикат Sat, и ответить на вопрос о его принадлежности классу Р. Если он принадлежит классу Р, то Р = NP в силу NP-полноты рассматриваемого предиката, если не принадлежит, то Р ф NP, так как найден предикат, принадлежащий NP и не принадлежащий Р. Но этот заманчивый план до сих пор реализовать не удалось, усилия многих исследователей не привели к решению этой проблемы, хотя и устоялось мнение, что, скорее всего, РФ NP. Это предположение влечет за собой рекомендацию: если доказано, что решаемая практическая задача (при надлежащей формализации в виде предиката на словах в алфавите) является NP-полной, то было бы опрометчивостью рассчитывать на нахождение в короткие сроки полиномиального алгоритма ее решения, и лучше попробовать решить эту задачу приближенно.
Многие задачи фактического построения некоторого математического объекта вписываются в следующую схему: дано х; если существует у такое, что х вместе с у удовлетворяют фиксированному условию R{x,y), то найти такое у. Соответствующая задача рас-
Огромное число примеров NP-полных задач собрано в [13].
208