- •Глава 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
Глава 5. Битовая сложность
за таким обозначением скрывается 0(/(m)logdm), где d — положительное число, значение которого не уточняется. Авторы показывают, что битовая сложность их алгоритма допускает оценку 0{т21/2), указывая при этом, что если верны некоторые известные в теории чисел гипотезы (для которых имеются серьезные основания полагать, что они верны), то можно взять г = 0{т2), и в этом случае сложность алгоритма в целом есть 0{ть).
На этом мы завершим разговор об алгоритме AKS, добавив лишь ко всему сказанному, что, например, в криптографии практикуются вероятностные (типа Монте-Карло) алгоритмы распознавания простоты, имеющие меньшую сложность, но не исключающие появления, хоть и с малой вероятностью, неверного ответа. В нашем курсе такого рода алгоритмы не рассматриваются1.
§ 23. Булева арифметика
Сложность булевых вычислений как сложность по числу булевых операций может рассматриваться как алгебраическая сложность. Но работа с булевыми величинами является фактически работой с битами, и сложность по числу булевых операций в этом смысле совпадает с битовой сложностью. Таким образом, для алгоритмов булевой арифметики алгебраическая сложность по числу булевых операций и битовая сложность —это одно и то же. Аналогично дело обстоит и с пространственной булевой (= битовой) сложностью.
Пример 23.1. Пусть дан ориентированный граф G = {V, E),n = \V\. Пусть С = (су) — булева матрица смежности графа G: сц = 1, если и только если i-я вершина соединена ребром с j-й, i,j = 1, 2,..., п. Требуется построить для G его матрицу связности D = (di;): dy = 1, если и только если i = j или i-я вершина соединена путем из одного или более ребер с j-й, i,j = 1, 2,..., п. Если рассматривать G как граф некоторого бинарного отношения на множестве из п элементов, то задачу можно интерпретировать как задачу построения транзитив-но-рефлексивного замыкания данного бинарного отношения. Соответственно, граф, для которого D является матрицей смежности, называют транзитивно-рефлексивным замыканием графа G, а саму матрицу D — транзитивно-рефлексивным замыканием матрицы С. Для матрицы D используется обозначение С*. На рис. 20 показан ориентированный граф и его транзитивно-рефлексивное замыкание. Соот-
1 По поводу этих алгоритмов распознавания простоты числа см. [21, гл. 33] и [8, гл. 4].
§ 23. Булева арифметика
151
б)
1
4
2 Л
5
Рис. 20. а) Ориентированный граф; б) его транзитивно-рефлексивное замыкание.
ветствующие матрицы C и C∗ выглядят следующим образом
С
° |
1 |
0 |
л |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
о |
0 |
0 |
о |
С*
1 |
1 |
1 |
л |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
о |
0 |
0 |
1 |
Нам понадобятся произведения булевых матриц, которые определяются как обычно: например, произведение F квадратных матриц A и B порядка n определяется формулой
fij = \/(aikAbkj), i,j = 1,2,
k=i
Элемент с индексами i,j для краткости будем называть (i, Л-элемен-том матрицы.
Легко видеть, что С2 = СлС—это матрица, для которой (i, j)-эле-мент равен 1, если и только если i-я вершина соединена с j-й путем длины 2 (т.е. состоящим из двух ребер). Аналогично, Ск— матрица, для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путем длины к. Пусть / — матрица, для которой (i, Л-элемент равен 1, если и только если i = j. Тогда
c*=ivcvc2v...vcn-\
Индукцией по к несложно доказать, что для любой квадратной булевой матрицы С и натурального к выполнено
/VCvC2V...VCfc = (7vC)fc. (23.1)
Это дает нам
C* = (lv СУ-1. (23.2)
152