принцип Яо

В теории вычислительной сложности принцип Яо (также называемый принципом минимакса Яо или леммой Яо ) связывает производительность рандомизированных алгоритмов с детерминированными (неслучайными) алгоритмами. Он утверждает, что для определенных классов алгоритмов и определенных мер производительности алгоритмов следующие две величины равны:

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

Принцип Яо часто используется для доказательства ограничений производительности рандомизированных алгоритмов путем нахождения распределения вероятностей на входных данных, которое является сложным для детерминированных алгоритмов, и вывода о том, что рандомизированные алгоритмы имеют те же ограничения производительности в худшем случае. ^[1]

Этот принцип назван в честь Эндрю Яо , который впервые предложил его в статье 1977 года. ^[2] Он тесно связан с теоремой о минимаксе в теории игр с нулевой суммой и с теорией двойственности линейных программ .

Рассмотрим любую меру стоимости алгоритма на входе , например, время его выполнения, для которого мы хотим изучить ожидаемое значение по рандомизированным алгоритмам и случайным входам. Рассмотрим также любой конечный набор детерминированных алгоритмов (сделанный конечным, например, путем ограничения алгоритмов определенным размером входа) и конечный набор входов для этих алгоритмов. Пусть обозначает класс рандомизированных алгоритмов, полученных из распределений вероятностей по детерминированным поведениям в , и пусть обозначает класс распределений вероятностей на входах в . Тогда принцип Яо гласит, что: ^[1]${\displaystyle c(A,x)}$${\displaystyle А}$${\displaystyle x}$ ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {X}}}$

$${\displaystyle \max _{D\in {\mathcal {D}}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$

Здесь — обозначение ожидаемого значения, а означает, что — случайная величина, распределенная по закону . Конечность и позволяет интерпретировать и как симплексы векторов вероятностей , [ ^3] компактность которых подразумевает существование минимумов и максимумов в этих формулах. ^[4]${\displaystyle \mathbb {E} }$${\displaystyle x\сим D}$${\displaystyle x}$${\displaystyle D}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {R}}}$

Более слабая форма того же принципа, как неравенство, а не равенство, преобразует любое жесткое распределение входных данных для детерминированных алгоритмов в нижнюю границу стоимости всех рандомизированных алгоритмов. Если — любой конкретный выбор жесткого распределения входных данных, а — любой конкретный рандомизированный алгоритм в , то ^[1] То есть, наилучшая возможная детерминированная производительность по распределению — это нижняя граница производительности любого рандомизированного алгоритма по его наихудшему входному случаю. Можно также наблюдать эту более слабую версию принципа Яо напрямую, как по линейности ожидания и принципу, что для любого распределения. Избегая максимизации и минимизации по и , эта версия принципа Яо может применяться в некоторых случаях, когда или не являются конечными. ^[5] Однако версия принципа Яо, использующая равенство, а не неравенство, также может быть полезна при доказательстве нижних границ рандомизированных алгоритмов. Равенство подразумевает, что при доказательстве нижних границ таким способом не теряется общность: каким бы ни был фактический наилучший рандомизированный алгоритм, существует некоторое входное распределение, с помощью которого может быть доказана соответствующая нижняя граница его сложности. ^[6]${\displaystyle D\in {\mathcal {D}}}$${\displaystyle R}$${\displaystyle {\mathcal {R}}}$$${\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$${\displaystyle D}$${\displaystyle R}$$${\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)],}$$${\displaystyle \min \leq \mathbb {E} \leq \max }$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {A}}}$

Когда стоимость обозначает время выполнения алгоритма, принцип Яо утверждает, что наилучшее возможное время выполнения детерминированного алгоритма на жестком входном распределении дает нижнюю границу для ожидаемого времени любого алгоритма Лас-Вегаса на его худшем входном случае. Здесь алгоритм Лас-Вегаса является рандомизированным алгоритмом, время выполнения которого может варьироваться, но для которого результат всегда правильный. ^{[7] [8]} Например, эта форма принципа Яо использовалась для доказательства оптимальности некоторых алгоритмов поиска по дереву Монте-Карло для точной оценки игровых деревьев . ^[8]${\displaystyle с}$

Временная сложность алгоритмов сортировки и выбора на основе сравнения часто изучается с использованием числа сравнений между парами элементов данных в качестве заменителя для общего времени. Для этих задач для любого фиксированного числа элементов входные данные могут быть выражены как перестановка , а детерминированный алгоритм может быть выражен как дерево решений , оба конечны по числу, как того требует принцип Яо. Аргумент симметризации определяет самые сложные входные распределения: это случайные перестановки , распределения по отдельным элементам, для которых все перестановки одинаково вероятны. Это потому, что если бы любое другое распределение было самым сложным, его усреднение со всеми перестановками того же самого жесткого распределения было бы одинаково сложным и дало бы распределение для случайной перестановки. Принцип Яо расширяет нижние границы для среднего числа случаев сравнений, сделанных детерминированными алгоритмами для случайных перестановок, до анализа наихудшего случая рандомизированных алгоритмов сравнения. ^[2]${\displaystyle n}$

Пример, приведенный Яо, — это анализ алгоритмов для нахождения наибольшего из заданного набора значений, проблема выбора. ^[2] Впоследствии, в соответствии с работой Яо, Уолтер Кунто и Ян Манро показали, что для случайных перестановок любой детерминированный алгоритм должен выполнять по крайней мере ожидаемое количество сравнений. ^[9] Согласно принципу Яо, такое же количество сравнений должно быть выполнено рандомизированными алгоритмами на их наихудшем входе. ^[10] Алгоритм Флойда–Ривеста попадает в пределы сравнений этой границы. ^[11]${\displaystyle к}$${\displaystyle n}$${\ displaystyle n+ \ min (k, nk) -O (1)}$${\displaystyle O({\sqrt {n\log n}})}$

Другим оригинальным применением Яо его принципа было изучение уклончивости свойств графа , количества тестов смежности пар вершин, необходимых для определения того, обладает ли граф заданным свойством, когда единственный доступ к графу осуществляется через такие тесты. ^[2] Ричард М. Карп предположил, что каждый рандомизированный алгоритм для каждого нетривиального монотонного свойства графа (свойства, которое остается верным для каждого подграфа графа с этим свойством) требует квадратичного числа тестов, но были доказаны только более слабые границы. ^[12]

Как заявил Яо, для свойств графа, которые верны для пустого графа, но ложны для некоторого другого графа на вершинах с ограниченным числом ребер, рандомизированный алгоритм должен проверять квадратичное число пар вершин. Например, для свойства быть планарным графом , потому что граф полезности с 9 ребрами непланарен. Точнее, Яо утверждает, что для этих свойств, по крайней мере, необходимы тесты, для каждого , чтобы рандомизированный алгоритм имел вероятность не более совершить ошибку. Яо также использовал этот метод, чтобы показать, что квадратично много запросов необходимо для свойств содержания заданного дерева или клики в качестве подграфа, содержания идеального паросочетания и содержания гамильтонова цикла , для достаточно малых постоянных вероятностей ошибок. ^[2]${\displaystyle n}$${\displaystyle с}$${\displaystyle s=9}$${\displaystyle \left({\tfrac {1}{2}}-p\right){\tfrac {1}{s}}{\tбином {n}{2}}}$${\displaystyle \varepsilon >0}$${\displaystyle p}$

В оптимизации черного ящика проблема заключается в определении минимального или максимального значения функции из заданного класса функций, доступных только через вызовы функции на аргументах из некоторой конечной области. В этом случае стоимость, подлежащая оптимизации, — это количество вызовов. Принцип Яо был описан как «единственный доступный метод для доказательства нижних границ для всех эвристик рандомизированного поиска для выбранных классов задач». ^[13] Результаты, которые могут быть доказаны таким образом, включают следующее:

• Для булевых функций на -битных двоичных строках, которые проверяют, равен ли вход некоторой фиксированной, но неизвестной строке, оптимальное ожидаемое число вызовов функций, необходимых для нахождения неизвестной строки, равно . Этого можно достичь с помощью функции, которая проверяет строки в случайном порядке, и это доказано оптимальным с помощью принципа Яо на входном распределении, который выбирает равномерно случайную функцию из этого класса. ^[13]${\displaystyle n}$${\displaystyle 2^{n-1}+{\tfrac {1}{2}}}$
• Унимодальная функция от -битных двоичных строк до действительных чисел определяется следующим свойством: для каждой входной строки , либо является уникальным максимальным значением , либо может быть изменена в одном бите на строку с большим значением. Таким образом, локальный поиск , который изменяет один бит за раз, когда это дает большее значение, всегда в конечном итоге найдет максимальное значение. Такой поиск может занять экспоненциально много шагов, но ничего существенно лучшего невозможно. Для любого рандомизированного алгоритма, который выполняет запросы, некоторая функция в этом классе приведет к тому, что алгоритм будет иметь экспоненциально малую вероятность нахождения максимума. ^[13]${\displaystyle f}$${\displaystyle n}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle у}$${\displaystyle 2^{o(n)}}$

В сложности связи алгоритм описывает протокол связи между двумя или более сторонами, а его стоимость может быть числом битов или сообщений, переданных между сторонами. В этом случае принцип Яо описывает равенство между средней сложностью детерминированных протоколов связи, на входном распределении, которое является наихудшим случаем для проблемы, и ожидаемой сложностью связи рандомизированных протоколов на их наихудших входных данных. ^{[6] [14]}

Пример, описанный Ави Вигдерсоном (основанный на статье Ману Виолы), — это сложность коммуникации для двух сторон, каждая из которых содержит -битные входные значения, чтобы определить, какое значение больше. Для детерминированных протоколов коммуникации нет ничего лучше битов коммуникации, что легко достигается одной стороной, отправляющей все свои входные данные другой. Однако стороны с общим источником случайности и фиксированной вероятностью ошибки могут обмениваться 1-битными хэш - функциями префиксов ввода, чтобы выполнить шумный бинарный поиск для первой позиции, где их входные данные различаются, достигая битов коммуникации. Это находится в пределах постоянного множителя оптимальности, как можно показать с помощью принципа Яо с распределением ввода, которое выбирает позицию первой разницы равномерно случайным образом, а затем выбирает случайные строки для общего префикса до этой позиции и остальных входных данных после этой позиции. ^{[6] [15]}${\displaystyle n}$${\displaystyle n}$${\displaystyle O(\log n)}$

Принцип Яо также был применен к конкурентному соотношению онлайн-алгоритмов . Онлайн-алгоритм должен отвечать на последовательность запросов, не зная о будущих запросах, неся некоторые затраты или прибыль за запрос в зависимости от своего выбора. Конкурентное соотношение - это отношение его затрат или прибыли к значению, которое может быть достигнуто автономным алгоритмом с доступом к знаниям обо всех будущих запросах, для наихудшей последовательности запросов, которая заставляет это соотношение быть как можно дальше от единицы. Здесь нужно быть осторожным, чтобы сформулировать соотношение с производительностью алгоритма в числителе и оптимальной производительностью автономного алгоритма в знаменателе, так что мера стоимости может быть сформулирована как ожидаемое значение, а не как обратная величина ожидаемого значения. ^[5]

Пример, приведенный Бородиным и Эль-Янивом (2005), касается алгоритмов замены страниц , которые отвечают на запросы страниц памяти компьютера, используя кэш страниц, для заданного параметра . Если запрос соответствует кэшированной странице, он ничего не стоит; в противном случае одна из кэшированных страниц должна быть заменена запрошенной страницей, по стоимости одной ошибки страницы . Сложное распределение последовательностей запросов для этой модели может быть сгенерировано путем выбора каждого запроса равномерно случайным образом из пула страниц. Любой детерминированный онлайн-алгоритм имеет ожидаемые ошибки страниц, по запросам. Вместо этого автономный алгоритм может разделить последовательность запросов на фазы, в которых используются только страницы, подвергаясь только одной ошибке в начале фазы, чтобы заменить одну страницу, которая не используется в течение фазы. Как пример проблемы сборщика купонов , ожидаемые запросы на фазу составляют , где - th гармоническое число . Согласно теории обновления , автономный алгоритм с высокой вероятностью вызывает ошибки страниц, поэтому конкурентное отношение любого детерминированного алгоритма против этого входного распределения составляет по крайней мере . Согласно принципу Яо, также нижние границы конкурентного отношения любого рандомизированного алгоритма замены страниц против последовательности запросов, выбранной не подозревающим противником в качестве наихудшего случая для алгоритма, но без знания случайных выборов алгоритма. ^[16]${\displaystyle к}$${\displaystyle к}$${\displaystyle к+1}$${\displaystyle {\tfrac {n}{k+1}}}$${\displaystyle n}$${\displaystyle к}$${\displaystyle (k+1)H_{k}}$${\displaystyle H_{k}=1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{k}}}$${\displaystyle к}$${\displaystyle {\tfrac {n}{(k+1)H_{k}}}+o (n)}$${\displaystyle H_{k}}$${\displaystyle H_{k}}$

Для онлайн-задач общего класса, связанных с проблемой проката лыж , Сейден предложил метод «поваренной книги» для получения оптимально жестких распределений входных данных на основе определенных параметров задачи. ^[17]

Принцип Яо можно интерпретировать в терминах теории игр , через игру с нулевой суммой для двух игроков , в которой один игрок, Алиса , выбирает детерминированный алгоритм, другой игрок, Боб, выбирает входные данные, а выигрыш — это стоимость выбранного алгоритма на выбранных входных данных. Любой рандомизированный алгоритм можно интерпретировать как рандомизированный выбор среди детерминированных алгоритмов и, таким образом, как смешанную стратегию для Алисы. Аналогично, неслучайный алгоритм можно рассматривать как чистую стратегию для Алисы. В любой игре с нулевой суммой для двух игроков, если один игрок выбирает смешанную стратегию, то у другого игрока есть оптимальная чистая стратегия против него. По теореме Джона фон Неймана о минимаксе существует игровое значение и смешанные стратегии для каждого игрока, такие, что игроки могут гарантировать ожидаемое значение или лучше, играя этими стратегиями, и такие, что оптимальная чистая стратегия против любой смешанной стратегии дает ожидаемое значение точно . Таким образом, минимаксная смешанная стратегия для Алисы, установленная против лучшей противостоящей чистой стратегии для Боба, дает то же самое ожидаемое значение игры, что и минимаксная смешанная стратегия для Боба, установленная против лучшей противостоящей чистой стратегии для Алисы. Это равенство ожидаемых значений игры для игры, описанной выше, является принципом Яо в ​​его форме равенства. ^[5] Статья Яо 1977 года, первоначально формулирующая принцип Яо, доказала его таким образом. ^[2]${\displaystyle R}$${\displaystyle с}$${\displaystyle с}$${\displaystyle с}$${\displaystyle с}$

Оптимальная смешанная стратегия для Алисы (рандомизированный алгоритм) и оптимальная смешанная стратегия для Боба (жесткое распределение входных данных) могут быть вычислены с использованием линейной программы, которая имеет вероятности одного игрока в качестве своих переменных, с ограничением на значение игры для каждого выбора другого игрока. Две линейные программы, полученные таким образом для каждого игрока, являются двойственными линейными программами , равенство которых является примером двойственности линейного программирования. ^[3] Однако, хотя линейные программы могут быть решены за полиномиальное время , количество переменных и ограничений в этих линейных программах (количество возможных алгоритмов и входных данных) обычно слишком велико, чтобы перечислить их явно. Поэтому формулирование и решение этих программ для нахождения этих оптимальных стратегий часто непрактично. ^{[13] [14]}

Для алгоритмов Монте-Карло , алгоритмов, которые используют фиксированное количество вычислительных ресурсов, но которые могут давать ошибочный результат, форма принципа Яо применяется к вероятности ошибки, частоте ошибок алгоритма. Выбор максимально возможного входного распределения и алгоритма, который достигает минимальной частоты ошибок по сравнению с этим распределением, дает ту же частоту ошибок, что и выбор оптимального алгоритма и его наихудшего входного распределения. Однако жесткие входные распределения, найденные таким образом, не являются устойчивыми к изменениям параметров, используемых при применении этого принципа. Если входное распределение требует высокой сложности для достижения определенной частоты ошибок, оно, тем не менее, может иметь неожиданно низкую сложность для другой частоты ошибок. Бен-Дэвид и Блейс показывают, что для булевых функций при многих естественных мерах вычислительной сложности существует входное распределение, которое одновременно является жестким для всех частот ошибок. ^[18]

Варианты принципа Яо также рассматривались для квантовых вычислений . Вместо рандомизированных алгоритмов можно рассмотреть квантовые алгоритмы, которые имеют хорошую вероятность вычисления правильного значения для каждого входа (вероятность не менее ); это условие вместе с полиномиальным временем определяет класс сложности BQP . Не имеет смысла спрашивать о детерминированных квантовых алгоритмах, но вместо этого можно рассмотреть алгоритмы, которые для заданного распределения входных данных имеют вероятность 1 вычисления правильного ответа, либо в слабом смысле, что входные данные, для которых это верно, имеют вероятность , либо в сильном смысле, в котором, кроме того, алгоритм должен иметь вероятность 0 или 1 генерации любого конкретного ответа на оставшихся входных данных. Для любой булевой функции минимальная сложность квантового алгоритма, который является правильным с вероятностью против его наихудшего входа, меньше или равна минимальной сложности, которая может быть достигнута для жесткого распределения входных данных с помощью наилучшего слабого или сильного квантового алгоритма против этого распределения. Слабая форма этого неравенства находится в пределах постоянного множителя от равенства, а сильная форма — нет. ^[19]${\displaystyle {\tfrac {2}{3}}}$${\displaystyle \geq {\tfrac {2}{3}}}$${\displaystyle \geq {\tfrac {2}{3}}}$