Цель рандомизации / дерандомизации в базовом рандомизированном алгоритме для MAX SAT

Question

В Разделах 5.1 настоящего Разработка алгоритмов аппроксимации Уильямсон и Шмойс описывают базовый рандомизированный алгоритм для MAX SAT и способы его дерандомизации.Алгоритм состоит просто в том, чтобы присвоить каждой переменной 1 (true) с вероятностью 1/2 и 0 (false) с вероятностью 1/2.Другими словами, выборка производится равномерно случайным образом из пространства всех решений.Они показывают, что это 1/2-приближение.

Затем в разделе 5.2 они описывают, как дерандомизировать его, используя метод условных ожиданий.(Я не буду описывать здесь этот процесс, потому что он, как я полагаю, не очень сложный и широко известный.)

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

Мне кажется, что столь же хорошим алгоритмом был бы однострочный, который детерминистически устанавливает все переменные равными 1.Учитывая некоторый МАКСИМАЛЬНЫЙ экземпляр SAT в качестве входных данных, мне кажется, что вы также ожидаете, что это (т. Е. "в ожидании, что это будет") удовлетворит половине предложений.Мне кажется, анализ случайного алгоритма действительно говорит о том, что любое фиксированное предположение является "хорошим". (Вместо того, чтобы показывать, что наш случайный алгоритм по своей сути хорош.) Так зачем же вообще проходить через процесс рандомизации и дерандомизации?

Заранее спасибо!

Answer 1

Разница в том, что рандомизированный алгоритм гарантирует ожидаемое приближение 1/2 при любом вводе.Напротив, противнику легко создать входные данные (т.е.экземпляр MAX-SAT), для которого детерминированный алгоритм "установить всем переменным значение true" удовлетворяет нулевым предложениям.

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

Что такое вспомогательные случайные биты?

Предположим, у нас есть рандомизированная машина Тьюринга $M_1$ который выполняется на экземплярах длины $n$ не более чем за $T(n)$ время, в течение которого он совершает не более $R(n) \le T(n)$ случайные решения.Мы можем превратить эту машину в детерминированный Машина Тьюринга $M_2$ который имеет две входные ленты:обычная лента, содержащая входную строку $x$ длины $n$, и лента , содержащая строку $r$ длины $R(n)$.Строка $r$ это наша цепочка вспомогательные случайные биты;он определяет, какие "случайные" решения должна принимать машина Тьюринга.Когда мы говорим, что рандомизированная машина Тьюринга запускается $M_1(x)$ принимает с вероятностью $p$, это эквивалентно утверждению , что множество $$A(x) = \left\{r\ |\ r \in \{0, 1\}^{R(|x|)}, M_2(x, r) ext{ принимает} ight\}$$ из $r$ строки , которые создают $M_2(x, r)$ принятие составляет долю $p = |A(x)| / 2^{|x|}$ из множества всех $r$ струны.

Возможно, вы поймете, что здесь происходит, если видели аналогичную конструкцию для недетерминированных машин Тьюринга.Мы можем думать о NP-машине как о недетерминированной машине, которая разветвляется на экспоненциально большое количество копий самой себя.Но мы также можем думать об этом как о детерминированном верификатор машина, для которой требуются как входные данные, так и строка "proof", с критериями приемлемости, чтобы строка ввода была на том языке, на котором Любой пробная строка заставляет машину согласиться.

Часто проще подумать об этой приземленной концепции детерминированных машин-верификаторов и о том, какое подмножество строк доказательств заставляет машину принимать данные входные данные, вместо того, чтобы думать об очень абстрактных идеях, таких как экспоненциально ветвящиеся машины и возможные миры.И это упрощает определение классов сложности, таких как co-NP, PP, BPP, ⊕P и т.д., Все из которых по сути являются "NP с другим правилом принятия". Например:

• NP - это набор языков $L$ для которого существует машина проверки за полиномиальное время $M_2$ такой , что $x \в L$ тогда и только тогда, когда существует $r$ строка такая , что $M_2(x, r)$ принимает (где длина $r$ строка ограничена многочленом $R(|x|)$).
• BPP - это набор языков $L$ для которого существует машина проверки за полиномиальное время $M_2(x, r)$ такой , что $x \в L$ подразумевает , что $M_2(x, r)$ принимается по крайней мере для ⅔ из $r$ струны и $x \нотин L$ подразумевает , что $M_2(x, r)$ принимается не более чем за ⅓ из $r$ строки (где длина $r$ строки ограничены многочленом $R(|x|)$).

Примечание:В основном не имеет значения, требуем ли мы $r$ строки должны иметь длину именно так $R(n)$ или самое большее $R(n)$, поскольку разрешение более коротких строк только увеличивает количество возможных строк на постоянный коэффициент.