Глава 5. Битовая сложность

за таким обозначением скрывается 0(/(m)log^dm), где d — положи­тельное число, значение которого не уточняется. Авторы показывают, что битовая сложность их алгоритма допускает оценку 0{т^21/2), ука­зывая при этом, что если верны некоторые известные в теории чисел гипотезы (для которых имеются серьезные основания полагать, что они верны), то можно взять г = 0{т²), и в этом случае сложность алгоритма в целом есть 0{т^ь).

На этом мы завершим разговор об алгоритме AKS, добавив лишь ко всему сказанному, что, например, в криптографии практикуются вероятностные (типа Монте-Карло) алгоритмы распознавания про­стоты, имеющие меньшую сложность, но не исключающие появле­ния, хоть и с малой вероятностью, неверного ответа. В нашем курсе такого рода алгоритмы не рассматриваются¹.

§ 23. Булева арифметика

Сложность булевых вычислений как сложность по числу булевых опе­раций может рассматриваться как алгебраическая сложность. Но ра­бота с булевыми величинами является фактически работой с бита­ми, и сложность по числу булевых операций в этом смысле совпа­дает с битовой сложностью. Таким образом, для алгоритмов булевой арифметики алгебраическая сложность по числу булевых операций и битовая сложность —это одно и то же. Аналогично дело обстоит и с пространственной булевой (= битовой) сложностью.

Пример 23.1. Пусть дан ориентированный граф G = {V, E),n = \V\. Пусть С = (су) — булева матрица смежности графа G: с_ц = 1, если и только если i-я вершина соединена ребром с j-й, i,j = 1, 2,..., п. Требуется построить для G его матрицу связности D = (d_i;): d_y = 1, если и только если i = j или i-я вершина соединена путем из одного или более ребер с j-й, i,j = 1, 2,..., п. Если рассматривать G как граф некоторого бинарного отношения на множестве из п элементов, то задачу можно интерпретировать как задачу построения транзитив-но-рефлексивного замыкания данного бинарного отношения. Соот­ветственно, граф, для которого D является матрицей смежности, на­зывают транзитивно-рефлексивным замыканием графа G, а саму мат­рицу D — транзитивно-рефлексивным замыканием матрицы С. Для матрицы D используется обозначение С*. На рис. 20 показан ориен­тированный граф и его транзитивно-рефлексивное замыкание. Соот-

¹ По поводу этих алгоритмов распознавания простоты числа см. [21, гл. 33] и [8, гл. 4].

§ 23. Булева арифметика

151

б)

1

а)

4

2 Л 5

3

Рис. 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 = \/(a_ikAb_kj), i,j = 1,2,

k=i

Элемент с индексами i,j для краткости будем называть (i, Л-элемен-том матрицы.

Легко видеть, что С² = СлС—это матрица, для которой (i, j)-эле-мент равен 1, если и только если i-я вершина соединена с j-й путем длины 2 (т.е. состоящим из двух ребер). Аналогично, С^к— матрица, для которой (i, j)-элемент равен 1, если и только если i-я верши­на соединена с j-й путем длины к. Пусть / — матрица, для которой (i, Л-элемент равен 1, если и только если i = j. Тогда

c*=ivcvc²v...vcⁿ-\

Индукцией по к несложно доказать, что для любой квадратной буле­вой матрицы С и натурального к выполнено

/VCvC²V...VC^fc = (7vC)^fc. (23.1)

Это дает нам

C* = (lv СУ-¹. (23.2)

152