Рандомизированные алгоритмы конструктивны?

Question

Из того, что доказательства вероятностным методом часто считаются неконструктивными.

Однако доказательство вероятностным методом действительно разрабатывает рандомизированный алгоритм и использует его для доказательства существования. Цитируется из P103 Рандомизированные алгоритмы Раджива Мотвани, Прабхакар Рагхаван:

Мы могли бы рассматривать доказательство вероятностным методом как рандомизированный алгоритм. Затем это потребует дальнейшего анализа, ограничивающего вероятность того, что алгоритм не может найти хорошего разделения при данном исполнении. Основное различие между мысленным экспериментом в вероятностном методе и рандомизированным алгоритмом - это конец, который каждый дает. Когда мы используем вероятностный метод, мы заинтересованы только в том, чтобы показать, что комбинаторный объект существует; Таким образом, мы довольны тем, что благоприятное событие происходит с ненулевой вероятностью. С помощью рандомизированного алгоритма, с другой стороны, эффективность является важным соображением - мы не можем переносить минускую вероятность успеха.

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

Как определяется алгоритм или доказательство «конструктивного»?

Спасибо!

Answer 1

Вероятностный метод обычно используется, чтобы показать, что вероятность немного Случайный объект, обладающий определенным свойством, является ненулевым, но не показывает никаких примеров. Это гарантирует, что алгоритм «повторного до-успеха» в конечном итоге прекратится, но не дает верхней границы во время выполнения. Таким образом, если вероятность удержания имущества не является существенной, доказательство существования с вероятностным методом не составляет очень плохой алгоритм.

На самом деле, вероятностные алгоритмы на самом деле не являются конструктивными доказательствами, так как они являются алгоритмами производить Конструктивные доказательства. Вывод - это объект, который он должен был доказать существование; Но тот факт, что это будет в итоге Получите один («существует итерация, в которой она приведет пример - за исключением вероятности нулевой ...») недостаточно, чтобы быть конструктивной; Это будет удовлетворительно только для того, кто уже принимает, что ненулевой доходности недостаточно для существования. И наоборот, если у вас есть хорошее связанное время на время выполнения, то в принципе нет оправдания, чтобы не запускать его, чтобы фактически создать пример. Хороший вероятностный алгоритм все еще не конструктивным доказательством, но хорошим план Чтобы получить конструктивное доказательство.

Обратите внимание, что эта идея, что рандомизированный алгоритм Стратегия доказательства (В отличие от доказательства само по себе) для демонстрации экзистенциальной количественной оценки, мало чем отличается от идеи, что индукция является хорошей стратегией доказательства для демонстрации универсального количественного определения (над естественными числами). Эта аналогия может показаться убедительной, поскольку индукция по сути является сердцем рекурсии как вычислительной техники. (Для любого положительного целого числа $ n $, если вы хотите решить, является ли $ n^2 $ суммой последовательных нечетных чисел, предшествующих 2N+1 $+1 $, вы можете сократить это, чтобы расследовать, является ли $ (n-1) 2 $-это сумма последовательных нечетных чисел, предшествующих 2N-1 $, и т. Д.) Индукция, по сути, является алгоритмической стратегией, которую мы подняли в теорему, позволяя нам иметь знания, не явно вычислив ее каждый раз. Тем не менее, индукция принимается конструктивно, потому что она уже является аксиомой (-ххемой) арифметики Пеано, и та, которая не зависит от других аксиомов. Напротив, не существует правила вывода или аксиомы, которое позволяет вероятностному методу доказывать существование или конструктивно доказать, что вероятностные алгоритмы дают доказательства существования или что -либо вдоль этого. Вы просто не можете доказать, что существуют примеры класса объекта из того факта, что существует вероятностный алгоритм для его построения, если вы уже не принимаете это предложение, либо как аксиома, либо из других помещений.

Конечно, можно принять философское положение, промежуточное, чтобы конструктивизм и классический подход к существованию, и сказать, что то, что нужно, является не конструкциями как таковой, а строительной схемой, которым разрешено терпеть неудачу с любой вероятностью менее одного; Это сделало бы любую вероятностную конструкцию «схемой», если не полностью конструктивно. Когда кто-то хочет провести черту, сказать, что они находят доказательство существования «удовлетворительным», в конечном итоге зависит от того, насколько интуиция (в нефилософском смысле) они хотят получить от доказательств.

Answer 2

Форнальная сложность доказательства является полевой (среди прочего) поля (среди прочего) изучению конструктивных представлений о доказательствах и их связи с классами сложности. Для каждого из популярных (равномерных) классов сложности схемы можно определить теорию, в которой все, что доказывает, имеет «поддержку» в алгоритме в этом классе сложности. Рандомизированные алгоритмы проводятся через версии принципа голубей (как ни странно).

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