Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций

Подождите немного. Документ загружается.

Упражнение 51 Укажите как надо организовать вычисление, чтобы проверка на допустимость нового ре-

шения имела сложность O(m).

Таким образом, сложность алгоритма существенно зависит от размера множества допустимых решений, возника-

ющих при выполнении алгоритма.

Упражнение 52 Какие входные данные для алгоритма 28 «Упаковка-ДинПрог» заставят его работать экс-

поненциально долго? А какие — за O(n

Однако, можно показать, что алгоритм 28 «Упаковка-ДинПрог» может быть полиномиальным в среднем, т.е. ра-

ботать эффективно на некотором случайном распределении входных данных.

Предположим, что все элементы a

матрицы ограничений из (3.1) являются независимыми случайными величина-

ми, принимающими значения {0, 1}, причем для всех i, j выполнено

P {a

= 1} = p, P {a

= 0} = 1 − p.

При этом время работы алгоритма является случайной величиной, зависящей от исходных данных, и под средним

временем понимается математическое ожидание времени работы алгоритма.

Теорема 23 Пусть для входных данных задачи 23 «Packing» выполнено условие

≥ ln n (3.2)

Тогда алгоритм 28 «Упаковка-ДинПрог» является полиномиальным в среднем.

Доказательство Математическое ожидание времени работы алгоритма — O(nmE|T (n)|). Поэтому для доказатель-

ства теоремы 23 достаточно будет оценить сверху математическое ожидание размера множества T (n).

Вероятность P (k) того, что некоторый вектор x

с k единичными компонентами и n − k нулевыми компонентами

является допустимым решением (3.1) (то есть удовлетворяет всем ограничениям в (3.1)) можно оценить сверху следу-

ющим образом:

P (k) =

i=1

(k),

где p

(k) — вероятность выполнения i-неравенства для x

(k) ≡ P







j=1

≤ 1







≤ P







j=1

≤ 1







откуда (при k > 1)

P (k) ≤

i=1







j=1

≤ 1







i=1











j=1

= 0







+ P







j=1

= 1











i=1



(1 − p)

+ kp(1 − p)

k−1



i=1

(1 − p)

k−1

(1 + p(k −1)) ≤

i=1

(1 − p)

k−1

(1 + p)

k−1

i=1

(1 − p

)

k−1

≤

i=1

−p

(k−1)

= e

−mp

(k−1)

Упражнение 53 Докажите, что E|T (n)| ≤

k=0





P (k).

Следовательно, мы можем оценить математическое ожидание мощности T (n) следующим образом

E|T (n)| ≤

k=0





P (k) = 1 +

k=1





P (k) = 1 + n +

k=2





P (k)

= 1 + n +

k=2





−mp

(k−1)

≤ 1 + n +

k=2

k ln n−mp

(k−1)

= 1 + n + n

k=2

(k−1)(ln n−mp

)

При условии mp

≥ ln n в последней сумме каждый член не превосходит 1. Это и означает, что E|T (n)| = O(n

).2

В заключение отметим, что из полученных результатов вытекает не только полиномиальный в среднем алгоритм

для задачи оптимизации (3.1), но и полиномиальный в среднем алгоритм для, вообще говоря, более трудной задачи

подсчета числа целых точек в многограннике (3.1).

3.1.2 Точность жадного алгоритма для почти всех исходных данных

Анализ точности алгоритмов в типичном случае. Асимптотическая точность жадного алгоритма в зада-

че о покрытии для «почти всех исходных данных»

Ранее мы доказали, что для задачи о покрытии жадный алгоритм (см. раздел 2.1.1) в худшем случае гарантирует

нахождение покрытия, размер которого превосходит размер минимального покрытия не более чем в логарифмическое

число раз (по m).

Наша цель сейчас — показать, что для «типичных данных» (в отличие от худшего случая, см. упражнение 38) это

отношение близко к единице, т.е. размер покрытия, найденного жадным алгоритмом, почти равен размеру минималь-

ного покрытия.

Как и в предыдущем разделе, мы будем использовать формулировку задачи о покрытии на языке (0, 1)-матриц и

целочисленных линейных программ:

cx → min (3.3)

Ax ≥ b

∀i x

∈ {0, 1}

В этой целочисленной линейной программе n столбцов-переменных x

, . . . , x

соответствуют подмножествам S

, . . . , S

и их включению в решение-покрытие. Матрица A также является матрицей инцидентности, а векторы стоимости и

ограничений — также векторы размерности n и m соответственно, состоящие полностью из единиц.

Таким образом, m строк-ограничений, соответствующих m предметам, очевидным образом выражают ограничение

на обязательное включение предмета хотя бы в одно из покрывающих подмножеств, а целевая функция равна числу

таких подмножеств.

Как и в разделе 3.1.1, предположим, что A = (a

) — случайная (0,1)-матрица, такая, что для всех i, j выполнено

P {a

= 1} = p, P {a

= 0} = 1 − p.

Пусть R(G) =

, где Z

— величина покрытия найденного жадным алгоритмом, а M — величина минимального

покрытия. Наш основной результат заключается в следующей теореме.

Теорема 24 Пусть вероятность p фиксирована, 0 < p < 1. Пусть для задачи (3.3) со случайной матрицей A

определенной выше выполнены условия:

ln ln n

ln m

→ 0 при n → ∞, (3.4)

ln m

→ 0 при n → ∞. (3.5)

Тогда для любого фиксированного ε > 0

P{R(G) ≤ 1 + ε} → 1 при n → ∞.

Заметим, что при m = cn, где c — некоторая константа, условия (3.4) и (3.5) теоремы 24 выполнены автоматически.

Доказательство Сначала докажем нижнюю оценку размера минимального покрытия.

Пусть X — случайная величина, равная числу покрытий размера

= −d(1 − δ) ln m/ ln(1 − p)e,

тогда

EX =





P (l

где P (l

) — вероятность того, что фиксированные l

столбцов являются покрытием A. Нетрудно видеть (убедитесь, что

это действительно нетрудно!), что

P (l

) =



1 − (1 − p)



≤ exp{−m(1 − p)

Используя неравенство





≤ n

, получаем

ln EX ≤ l

ln n − m(1 − p)

≤ −

ln m

ln(1 − p)

ln n − m exp



−(1 − δ) ln(1 − p)

ln m

ln(1 − p)



≤ −

ln m

ln(1 − p)

ln n − mm

−1

≤ −

ln m

ln(1 − p)

ln n − m

Нетрудно проверить, что для любого фиксированного 0 < δ < 1 при условиях (3.4) последнее выражение стремится

к −∞ при n стремящемся к бесконечности.

Таким образом, вероятность того, что нет покрытия размера l

в случайной (0, 1)-матрице A стремится к 1, по-

скольку (согласно неравенству Чебышева)

P{X ≥ 1} ≤ EX → 0.

Последнее означает, что M ≥ l

Теперь докажем верхнюю оценку размера покрытия построенного жадным алгоритмом.

Используем следующую известную лемму [AS92] о вероятности больших уклонений для сумм независимых случай-

ных величин.

Лемма 21 Пусть Y — сумма n независимых случайных величин, каждая из которых принимает значение 1 с

вероятностью p и 0 с вероятностью 1 − p. Тогда

P{|Y − np| > δnp} ≤ 2 exp{−(δ

/3)np}.

По этой лемме вероятность того, что некоторый фиксированный столбец содержит менее чем (1 −δ)pn единиц (или

более чем (1 + δ)pn единиц) оценивается сверху так:

bad

≤ 2 exp{−(δ

/3)np},

и математическое ожидание числа таких столбцов не превосходит mP

bad

. Нетрудно видеть, что

bad

≤ 2 exp{ln m − (δ

/3)np} = 2 exp{ln m − O(1)n} → 0, при n → ∞,

по условию (3.5). Следовательно, первое неравенство Чебышева P {X ≥ 1} ≤ EX влечет, что вероятность события

«каждый столбец содержит не менее (1 − δ)pn единиц» стремится к 1.

Теперь мы можем почти дословно повторить получение верхней оценки размера покрытия, построенного жадным

алгоритмом, в худшем случае.

Пусть N

— число непокрытых строк после t-го шага жадного алгоритма. Имеем:

≤ N

t−1

−

t−1

(1 − δ)pn

= N

t−1

(1 − (1 − δ)p)

≤ N

(1 − (1 − δ)p)

= m(1 − (1 − δ)p)

Найдем максимальное t при котором еще есть непокрытый элемент:

m(1 − (1 − δ)p)

≥ 1

Получим:

ln m + t ln(1 − (1 − δ)p) ≥ 0,

или

t ≥ −

ln m

ln(1 − (1 − δ)p)

Отсюда получается верхняя оценка мощности «жадного покрытия» в типичном случае:

≤ 1 +

ln m

1−p(1−δ)

Упражнение 54 Докажите, что комбинируя это неравенство с нижней оценкой, можно получить что для

любого фиксированного ε > 0 и достаточно больших n

R(G) ≤ 1 + ε.

3.1.3 Полиномиальный в среднем алгоритм для задачи о рюкзаке

Рассмотрим снова классическую задачу о рюкзаке.

Вход: Положительные веса w

, . . . , w

, стоимости p

, . . . , p

, размер рюкзака B.

Выход: Подмножество S ⊆ [n] := {1, 2, . . . , n} такое что

i∈S

≤ B и

i∈S

— максимально.

Известно, что эта задача NP-трудна, если рассматривать ее с точки зрения худшего случая. Однако, было отмече-

но, что на практике некоторые из известных алгоритмов ее решения чрезвычайно эффективны. Одна из самых извест-

ных аналогий — это знаменитый симплекс-метод решения задачи линейного программирования, который на некоторых

входах работает экспоненциальное время, но в большинстве практических случаев чрезвычайно эффективен. Теоре-

тическое объяснение этого феномена заключается в том, что симплекс метод является полиномиальным в среднем

алгоритмом. Аналогичное положение (как выяснилось совсем недавно) имеет место быть и для задачи о рюкзаке.

Алгоритм Немхаузера-Ульмана

Мы рассмотрим сейчас алгоритм Немхаузера-Ульмана, основанный на методе динамического программирования, для

решения этой задачи и проанализируем его.

Определение: Подмножество S ⊆ [n] веса w(S) =

i∈S

и стоимости

i∈S

доминирует другое подмножество

T ⊆ [n] если w(S) ≤ w(T ) и p(S) ≥ p(T ).

Для i ∈ [n] пусть S(i) обозначает последовательность всех доминирующих подмножеств над 1, 2, . . . , i. Будем пред-

полагать, что множества в S(i) упорядочены по возрастанию их весов. Зная S(i) нетрудно найти S(i + 1) следующим

образом: сделаем еще одну копию S(i) и добавим элемент i+1 к каждому из элементов скопированного массива. Далее

сливаем два последовательных списка, удаляя множества доминируемые некоторым множеством из объединения двух

последовательностей. В результате получим S(i + 1). Обозначим q(n) = |S(n)|.

Лемма 1. Алгоритм Немхаузера-Ульмана вычисляет оптимум в задаче о рюкзаке за время

O (n · q(n)) .

Анализ

Теорема. Пусть веса w

являются произвольными положительными числами, а стоимости p

являются случайными

независимыми величинами равномерно распределенными на отрезке [0,1], и пусть q обозначает число доминирующих

множеств для всех n предметов. Тогда E[q] = O(n

Доказательство. Пусть m = 2

и S

, . . . , S

обозначают последовательность всех подмножеств множества [n],

перечисленных в порядке неубывания их весов. Пусть стоимость подмножества S

есть P

i∈S

. Для любого

2 ≤ u ≤ m, определим ∆

= max

k∈[u]

− max

k∈[u−1]

≥ 0.

Факт 1. Для любого u ≥ 2, S

— доминирующее множество тогда и только тогда когда ∆

> 0.

Имеем:

E[q] = P

u=2

Pr[∆

> 0].

Таким образом, для получения верхней оценки E[q] достаточно получить верхнюю оценку для

u=2

Pr[∆

> 0].

Для получения верхней оценки оценим E[P

]. С одной стороны,

E[P

] = P

u=2

E[∆

] =

u=2

Pr[∆

> 0]E[∆

| ∆

> 0].

С другой стороны, E[P

] = n/2. Справедлива следующая

Лемма 2. Для любого u ∈ {2, . . . , m}, E[∆

| ∆

> 0] ≥

32n

Отсюда следует, что

n/2 = E[P

] =

u=2

Pr[∆

> 0]E[∆

| ∆

> 0] ≥

u=2

Pr[∆

> 0] ·

32n

или E[q] = 1 +

u=2

Pr[∆

> 0] ≤ 16n

+ 1.

Таким образом, для получения окончательного результата остается доказать лемму 2.

Доказательство леммы 2. Зафиксируем u ∈ {2, . . . , m}. Заметим, что

E[∆

| ∆

> 0] ≥ Pr[∆

≥

16n

| ∆

> 0] ·

16n

Значит, достаточно доказать, что Pr[∆

≥

16n

| ∆

> 0] ≥

. Для каждого k ∈ [u − 1] положим X

= S

\ S

= S

\ S

. Имеем:

Pr[∆

≥

16n

| ∆

> 0] = Pr

∀k :

i∈S

≥

i∈S

16n

| ∀k :

i∈S

= Pr

∀k :

i∈X

≥

i∈Y

16n

| ∀k :

i∈X

≥

i∈Y

где квантор всеобщности распространяется на все элементы k ∈ [u − 1]. Без ограничения общности можно считать,

что S

= [t]. Рассмотрим два класса случайных переменных {p

, . . . , p

} и {p

t+1

, . . . , p

}. Пусть значения переменных

из второго класса фиксированы произвольным образом. Оценим вероятность того, что хотя бы одна из переменных из

первого класса мала.

∃j ∈ [t] : p

≤

| ∀k :

i∈X

≥

i∈Y

≤

j∈[t]

≤

| ∀k :

i∈X

≥

i∈Y

≤

j∈[t]



≤



≤

Далее предположим, что p

≥

, для любого j ∈ [t]. Пусть L

i∈X

. При нашем предположении L

≥

, для

любого k ∈ [u − 1], поскольку каждое множество X

содержит по крайней мере один элемент размера не менее

При наших предположениях о L

мы анализируем Pr



∆

16n

| ∆

> 0



. Для того, чтобы компенсировать слу-

чай, когда наше предположение не имеет места, мы докажем что эта вероятность не превосходит 1/4 (вместо 1/2). В

частности, перепишем уравнение (1) и докажем, что

∀k :

i∈Y

≤ L

−

16n

| ∀k :

i∈Y

≤ L

≥

для произвольного фиксированного L

≥

, где вероятность рассматривается по случайному выбору значений пере-

менных p

t+1

, . . . , p

Рассмотрим теперь геометрические интерпретации. Рассмотрим (n − t)-мерные политопы:

A =

(

t+1

× . . . × p

) ∈ [0, 1]

n−t

| ∀k :

i∈Y

≤ L

−

16n

)

B =

(

t+1

× . . . × p

) ∈ [0, 1]

n−t

| ∀k :

i∈Y

≤ L

)

Ясно, что A ⊆ B. Поскольку распределение равномерное,



∆

≥

16n

| ∆

> 0



vol(A ∩ B)

vol(B)

vol(A)

vol(B)

где vol(

) обозначает объем соответствующего политопа. В терминах объемов нам надо показать, что vol(A) ≥

vol(B).

Идея заключается в измельчении политопа B равномерно по всем размерностям пока измельченный политоп не

будет содержаться в политопе A. Для ε ∈ [0, 1] определим

(

t+1

× . . . × p

) ∈ [0, 1 − ε]

n−t

| ∀k :

i∈Y

≤ (1 − ε)L

)

Очевидно, B = B

и, в общем случае, B

может быть получен разбиением B по каждому измерению на множитель

1 − ε. Поскольку размерность равна n − t, vol(B

) = (1 − ε)

n−t

vol(B).

Далее мы исследуем вопрос о том, как выбрать ε так чтобы B

⊆ A. Заметим, что L

(1−

) ≤ L

−

16n

, поскольку

≥

. Полагая ε =

, получаем что B

⊆ A.

Далее имеем:

vol(A) ≥ vol(B

) = (1 − ε)

n−t

vol(B) ≥

(1 − ε(n − t))vol(B) ≥

vol(B),

что завершает доказательство леммы.

3.2 Вероятностные алгоритмы.

Напомним, что формальные (и неформальные) определения вероятностных алгоритмов и их классов мы рассматривали

в разделе 1.4.

3.2.1 Алгоритм Фрейвалда

Один из первых примеров вероятностных алгоритмов, более эффективных чем детерминированные, был предложен

Фрейвалдом (см. [MR95]) для задачи проверки матричного равенства AB = C. Обычный детерминированный алгоритм

заключается в перемножении матриц A и B и сравнении результата с C.

Сложность такого алгоритма есть O(n

) при использовании стандартного алгоритма умножения матриц размера

n × n, и O(n

2.376

) при использовании лучшего из известных быстрых алгоритмов матричного умножения.

Вероятностный алгоритм Фрейвалда для этой задачи имеет сложность O(n

) и заключается в умножении левой и

правой частей на случайный булев вектор x = (x

, . . . , x

) с последующим сравнением полученных векторов. Алго-

ритм выдает ответ, что AB = C, если ABx = Cx и является алгоритмом типа Монте-Карло с односторонней ошиб-

кой [MR95]. При этом ABx вычисляется как A(Bx), что и обеспечивает оценку сложности алгоритма O(n

Корректность алгоритма обеспечивается следующей теоремой.

Теорема 25 Пусть A, B, и C — n ×n матрицы над полем F

, причем AB 6= C. Тогда для случайного вектора x

выбранного случайно и равномерно из {0, 1}

P {ABx = Cx} ≤ 1/2.

Доказательство Пусть D = AB −C. Мы знаем, что D — не полностью нулевая матрица и хотим оценить вероятность

того, что Dx = 0. Без ограничения общности можно считать, что ненулевые элементы имеются в первой строке и они

располагаются перед нулевыми. Пусть d — вектор, равный первой строке матрицы D, и предположим, что первые k

элементов в d — ненулевые.

P{Dx = 0} ≤ P{d

x = 0}.

Но, d

x = 0 тогда и только тогда, когда

−

i=2

Для каждого выбора x

, . . . , x

правая часть этого равенства фиксирована и равна некоторому v > 0. Вероятность, что

равно v, не превосходит 1/2, поскольку x

равномерно распределено на двухэлементном множестве ({0, 1}).

Классическим примером задачи, где вероятностные алгоритмы успешно применяются, является задача проверки

тождеств для многочлена от многих переменных:

Задача 24 Верно ли для заданного полинома P (x

, . . . , x

), что P (x

, . . . , x

) ≡ 0?

Следующая лемма (См. [MR95]) по сути описывает вероятностный Монте-Карло алгоритм с односторонней ошиб-

кой.

элементы матрицы ∈ F

Лемма 22 Пусть Q(x

, . . . , x

) — многочлен от многих переменных степени d над полем F и пусть S ⊆ F —

произвольное подмножество. Если r

, . . . , r

выбраны случайно, независимо и равномерно из S, то

P (Q(r

, . . . , r

) = 0 | Q(x

, . . . , x

) 6≡ 0) ≤

|S|

Доказательство По индукции по n.

Базисный случай n = 1 включает полиномы от одной переменной Q(x

) степени d. Поскольку каждый такой поли-

ном имеет не более d корней, вероятность, что Q(r

) = 0 не превосходит

|S|

Пусть теперь предположение индукции верно для всех полиномов, зависящих от не более n − 1 переменной.

Рассмотрим полином Q(x

, . . . , x

) и разложим его по переменной x

Q(x

, . . . , x

) =

i=0

, . . . , x

где k ≤ d — наибольшая степень x

в Q.

Предполагая, что Q зависит от x

, имеем k > 0, и коэффициент при x

, Q

, . . . , x

) не равен тождественно нулю.

Рассмотрим две возможности.

Первая — Q

, . . . , r

) = 0. Заметим, что степень Q

не превосходит d − k, и по предположению индукции

вероятность этого события не превосходит

(d−k)

|S|

Вторая — Q

, . . . , r

) 6= 0. Рассмотрим следующий полином от одной переменной:

q(x

) = Q(x

, r

, . . . , r

) =

i=0

, . . . , r

Полином q(x

) имеет степень k, и не равен тождественно нулю, т.к. коэффициент при x

есть Q

, . . . , r

). Базо-

вый случай индукции дает, что вероятность события q(r

) = Q(r

, r

, . . . , r

) = 0 не превосходит

|S|

Мы доказали два неравенства:

P{Q

, . . . , r

) = 0} ≤

d − k

|S|

;

P{Q(r

, r

, . . . , r

) = 0| Q

, . . . , r

) 6= 0} ≤

|S|

Используя результат следующего упражнения: покажите, что для любых двух событий E

, E

P{E

} ≤ P{E

| E

} + P{E

мы получаем, что вероятность события Q(r

, r

, . . . , r

) = 0 не превосходит суммы двух вероятностей (d − k)/|S| и

k/|S|, что дает в сумме желаемое d/|S|. 2

Упражнение 55 Имеется квадратная, n × n матрица A, элементами которой являются линейные функции

(x) = a

x + b

Придумайте Монте-Карло алгоритм с односторонней ошибкой, для проверки этой матрицы на вырож-

денность (detA ≡ 0).

Еще одним примером успеха вероятностных алгоритмов является разработка эффективных вероятностных алго-

ритмов проверки простоты числа: для натурального числа n заданного в двоичной системе, определить является ли оно

простым [SV77]. Только в 2002 г. для этой задачи удалось построить полиномиальный детерминированный алгоритм.

Одной из многочисленных областей, где широко применяются вероятностные алгоритмы, являются параллельные

вычисления. Эффективным параллельным алгоритмом (или NC-алгоритмом) называется алгоритм, который на много-

процессорной RAM (так называемой PRAM) с числом процессоров не превосходящих некоторого полинома завершает

работу за время ограниченное полиномом от логарифма длины входа. Построение эффективного детерминированного

параллельного алгоритма (NC-алгоритма) для нахождения максимального паросочетания в двудольном графе являет-

ся одной из основных открытых проблем в теории параллельных алгоритмов. Удалось, однако, построить эффективный

параллельный вероятностный алгоритм нахождения максимального паросочетания в двудольном графе (так называе-

мый RNC-алгоритм) [MR95].

3.2.2 Вероятностные методы в перечислительных алгоритмах. Подсчет числа выполняю-

щих наборов для ДНФ

В данной лекции мы рассматриваем перечислительные задачи и изучим как вероятностные методы могут быть приме-

нены для решения таких задач. Алгоритм для решения перечислительной задачи берет на вход конкретные входные

данные рассматриваемой задачи (например граф) и в качестве выхода выдает неотрицательное целое являющееся чис-

лом решений задачи (например число гамильтоновых циклов в графе).

Далее мы опишем рандомизированную полиномиальную аппроксимационную схему для задачи подсчета числа вы-

полняющих наборов для данной днф, т.е. число наборов, на которых днф равна 1.

Пусть П - некоторая перечислительная задача, I - вход задачи. Пусть далее #(I) обозначает число различных

решений для входа I задачи П.

Определение 59 Полиномиальной рандомизированной аппроксимационной схемой (PRAS) для пере-

числительной задачи П называется вероятностный алгоритм A, который получая вход I и вещественное

ε > 0, за время полиномиальное от n = |I|выдает в качестве выхода A(I) такое, что

Pr[(1 − ε)#(I) ≤ A(I) ≤ (1 + ε)#(I)] ≥

Определение 60 Полностью полиномиальной рандомизированной аппроксимационной схемой

(FPRAS) называется полиномиальная рандомизированная аппроксимационная схема, время работы кото-

рой ограничено полиномом от n и 1/ε.

Определение. Полностью полиномиальной рандомизированной аппроксимационной схемой с параметрами (ε, δ)

(или кратко (ε, δ)-FPRAS) для перечислительной задачи П называется полностью полиномиальная рандомизирован-

ная аппроксимационная схема, которая на каждом входе I вычисляет ε-аппроксимацию для #(I) с вероятностью не

менее 1 − δ за время полиномиальное от n, 1/ε и log 1/δ.

Перечислительная задача для днф.

Пусть f (x

, . . . , x

) – булева формула в дизъюнктивной нормальной форме (днф) над множеством булевых пе-

ременных x

, . . . , x

. Иными словами f = C

∨ . . . ∨ C

есть дизъюнкция скобок C

, где каждая скобка C

есть

конъюнкция L

∧ . . . ∧ L

литералов. Каждый литерал есть либо переменная, либо ее отрицание.

Каждой булевой переменной приписывается значение из {0, 1}. Набор значений переменных a = (a

, . . . , a

) на-

зывается выполняющим для f если f (a

, . . . , a

) = 1.

Мы будем обозначать через #f число выполняющих наборов для данной формулы f .

Мы сформулируем более общую задачу и опишем для нее (ε, δ)-FPRAS.

Пусть U – конечное множество известной мощности и пусть f : U → {0, 1} булева функция над U . Положим G =

{u ∈ U | f (u) = 1}. Предположим, что для любого u ∈ U, f(u) можно вычислить эффективно. Предположим также,

что возможно равномерно и случайно выбирать элементы из U. Для простоты будем считать, что обе эти операции

занимают единичное время. Проблема заключается в оценке |G|.

Рассмотрим стандартный метод Монте-Карло и покажем, что он не является (ε, δ)-FPRAS для этой задачи.

1. Проведем N независимых испытаний, в каждом из которых выбирается случайная точка из U с равномерным

распределением. Если в i-м испытании в выбранной точке значение f равно 1, то полагаем y

= 1, в противном случае

полагаем y

= 0.

2. Рассмотрим сумму независимых случайных величин Y =

i=1

. В качестве аппроксимации |G| возьмем вели-

чину

G =

|U|.

Заметим, что P {y

= 1} = |G|/|U|. Обозначим эту вероятность через p. Справедливо следующее неравенство

Лемма ([MR95]. Пусть x

, . . . , x

– независимые случайные величины такие, что x

принимают значения 0, 1, и

P {x

= 1} = p, P {x

= 0} = 1 − p. Тогда для X =

i=1

и EX = np и для любого 0 < δ < 1, выполнены

неравенства:

P {X − EX > δEX} ≤ exp{−(δ

/3)EX}

P {X − EX < −δEX} ≤ exp{−(δ

/2)EX}.

Оценим вероятность того, что аппроксимация хорошая.

Pr{(1 − ε)|G| ≤

G ≤ (1 + ε)|G|} = Pr{(1 − ε)|G|N/|U| ≤ Y ≤ (1 + ε)|G|N/|U|} =

Pr{(1 − ε)Np ≤ Y ≤ (1 + ε)Np}.

Применяя неравенства из леммы, получаем:

Pr{(1 − ε)|G| ≤ Z ≤ (1 + ε)|G|} > 1 − 2 exp{−(ε

/3)Np}.

Накладываем условие, чтобы эта оценка была не меньше 1 − δ, и получаем:

2 exp{−(ε

/3)Np} < δ,

что эквивалентно

< exp{ε

/3Np}

или

N >

Почему полученная оценка не столь хороша? Потому что p может быть экспоненциально мало (например, если

функция равна 1 лишь в одной точке) и тогда число требующихся шагов будет экспоненциально велико.

Покажем как использовать этот метод не напрямую, а после некоторой переработки задачи.

Рассмотрим более общую (по сравнению с задачей о числе выполняющих наборов для днф) задачу.

Пусть V – конечное множество и имеется m его подмножеств H

, . . . , H

⊆ V удовлетворяющих следующим

условиям:

1. Для любого i, |H

| вычислимо в полиномиальное время;

2. Для любого i возможно выбрать случайно и равномерно элемент из H

;

3. Для любого v ∈ V возможно за полиномиальное время проверить верно ли, что v ∈ H

Нашей целью является оценка мощности объединения H = H

∪ . . . ∪ H

Определим U = {(v, i)| v ∈ H

}. Нетрудно видеть, что

|U| =

i=1

| ≥ |H|.

Для любого v ∈ H множество покрывающее v определяется так:

cov(v) = {(v, i)| (v, i) ∈ U}.

Мощность покрывающего множества в точности равна числу H

, содержащих v. В проблеме подсчета числа выполня-

ющих наборов для днф для набора a = (a

, . . . , a

), множество cov(a) является множеством скобок выполненных на a

(т.е. равных 1).

Нетрудно проверить следующие простые факты:

1. Число покрывающих множеств равно |H| и покрывающие множества легко вычислить;

2. Имеет место следующее разбиение U: U = ∪

v ∈H

cov(v);

3. |U| легко вычислить как |U| =

v ∈H

|cov(v)|;

4 Для любого v ∈ H, cov(v) ≤ m.

Определение. Функция F : U → {0, 1} определяется следующим образом:

F ((v, i)) = 1 тогда и только тогда когда i = min{j| v ∈ H

}, и нулю в противном случае.

Множество G определяется так:

G = {(v, j) ∈ U | F ((v, i)) = 1}.

Важное наблюдение заключается в том, что |G| = |H|.

Наша цель теперь заключается в оценке мощности G ⊆ U.

Лемма 1. Справедливо неравенство

ρ =

|G|

|U|

≥

Доказательство. Доказательство использует наблюдения, сделанные выше.

|U| =

v ∈H

|cov(v)| ≤

v ∈H

m ≤ m|H| = m|G|.

Далее применение стандартной техники метода Монте-Карло позволяет построить (ε, δ)-FPRAS для оценки |G|, и,

следовательно, и для |H|.

Теорема. Метод Монте-Карло дает (ε, δ)-FPRAS для оценки |G| при условии

N ≥

Время полиномиально по N.

Доказательство. Нам необходимо показать что F можно вычислить в полиномиальное время и можно эффективно

выбирать случайный элемент (равномерно) из U.

Для вычисления F ((v, i)) мы проверяем, верно ли, что набор значений переменных v является выполняющим для

, но не для C

, j < i.

Выбор случайного элемента (v, i) равномерно из U осуществляется в два этапа.

На первом этапе выберем i, 1 ≤ i ≤ m и

Pr[i] =

|U|

i=1

На втором этапе элемент v ∈ H

выбирается случайно и равномерно. Нетрудно проверить, что справедливо следующее

Утверждение 1. Получаемая пара (v, i) равномерно распределена в U .

Для доказательства достаточно перемножить соответствующие вероятности.

Далее воспользуемся классическим методом Монте-Карло. Из полученных ранее оценок имеем:

N >

Из леммы 1 следует, что 1/p ≤ m, откуда получаем, что достаточно провести N испытаний, где

N > m

Это и завершает доказательство теоремы.

Для исходной задачи перечисления выполняющих наборов для данной ДНФ имеем: базовое множество V состоит

из всех двоичных наборов длины n, H

состоит из всех наборов, на которых скобка C

равна 1 (выполнена). Ясно, что

| = 2

n−r

, где r

– число литералов в скобке C

. Нетрудно также организовать случайную выборку элемента из H

для этого достаточно зафиксировать значения переменных, входящих в конъюнкцию а остальные выбрать случайны-

ми. Проверка, что некоторое v ∈ V принадлежит H

, эквивалентно проверке выполнимости скобки (конъюнкции) на

данном наборе. Таким образом, все условия на H

выполнены и описанный метод аппроксимации дает (ε, δ)-FPRAS

для оценки числа выполняющих наборов для любой ДНФ.

Упражнения.

1. Докажите упражнение 1.

2. Докажите факт 2: U = ∪

v ∈H

cov(v).

3. Докажите, что для G = {(v, j) ∈ U| f((v, i)) = 1} верно равенство |G| = |H|.

3.2.3 Вероятностный алгоритм Луби нахождения максимального по включению независи-

мого множества в графе

Пусть G = (V, E) – неориентированный граф с n вершинами и m ребрами. Подмножество вершин I ⊆ V называется

независимым в G, если никакое ребро из E не содержит обе своих конечных вершины в I.

Определение: Независимое множество I называется максимальным по включению, если оно не содержится в

качестве собственного подмножества в другом независимом множестве в G.

Напомним, что задача нахождения максимального по мощности независимого множества NP-трудна. Однако, для

нахождения максимального по включению независимого множества существует тривиальный последовательный алго-

ритм с временной сложностью O(m).

Алгоритм Greedy MIS:

Вход: Граф G = (V, E) с V = {1, 2, . . . , n}.

Выход: Максимальное по включению множество I ⊆ V .

1. I := ∅.

2. для v = 1 до n выполнить

если I ∩ Γ(v) = ∅ то I := I ∪ {v}.

Лемма. Алгоритм Greedy MIS завершает работу после O(m) шагов и выдает максимальное по включению неза-

висимое множество, при условии, что граф на вход подается в виде списка смежности.

Проблема заключается в том, чтобы построить эффективный параллельный алгоритм для этой задачи. Мы будем

рассматривать модель PRAM (Parallel RAM), которая состоит из p процессоров с общим набором регистров (ячеек

памяти). Процессоры могут писать в память и читать из памяти независимо друг от друга. Ограничением является лишь

возможность писать или читать из одной ячейки для нескольких процессоров. Мы будем рассматривать самую слабую

модель — EREW PRAM (Exclusive Reed Exclusive Write PRAM), в которой процессоры могут читать одновременно

только из разных ячеек и писать в разные ячейки.

100