Средняя сложность случая

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

Существует три основных мотива для изучения сложности в среднем случае. ^[1] Во-первых, хотя некоторые проблемы могут быть неразрешимыми в худшем случае, входные данные, которые вызывают такое поведение, могут редко встречаться на практике, поэтому сложность в среднем случае может быть более точной мерой производительности алгоритма. Во-вторых, анализ сложности в среднем случае предоставляет инструменты и методы для создания сложных примеров проблем, которые могут быть использованы в таких областях, как криптография и дерандомизация . В-третьих, сложность в среднем случае позволяет различать наиболее эффективный алгоритм на практике среди алгоритмов эквивалентной сложности в лучшем случае (например, быстрая сортировка ).

Анализ среднего случая требует понятия «среднего» входа в алгоритм, что приводит к проблеме разработки распределения вероятностей по входам. В качестве альтернативы можно использовать рандомизированный алгоритм . Анализ таких алгоритмов приводит к связанному понятию ожидаемой сложности . ^[2]^{: 28}

История и предыстория

Средняя производительность алгоритмов изучалась с тех пор, как в 1950-х годах были разработаны современные понятия вычислительной эффективности. Большая часть этой первоначальной работы была сосредоточена на проблемах, для которых уже были известны алгоритмы с наихудшим полиномиальным временем. ^[3] В 1973 году Дональд Кнут ^[4] опубликовал третий том «Искусства программирования» , в котором подробно рассматривается средняя производительность алгоритмов для задач, решаемых за наихудшее полиномиальное время, таких как сортировка и поиск медианы.

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

Фундаментальные понятия сложности в среднем случае были разработаны Леонидом Левиным в 1986 году, когда он опубликовал одностраничную статью ^[5], в которой дал определение сложности в среднем случае и полноты, а также привел пример полной задачи для $distNP$ , аналога NP в среднем случае .

Определения

Эффективная сложность в среднем случае

Первая задача — точно определить, что подразумевается под алгоритмом, который эффективен «в среднем». Первоначальная попытка может определить эффективный алгоритм в среднем случае как тот, который выполняется за ожидаемое полиномиальное время на всех возможных входных данных. Такое определение имеет различные недостатки; в частности, оно неустойчиво к изменениям в вычислительной модели. Например, предположим, что алгоритм $A$ выполняется за время $t A (x)$ на входных данных $x$ , а алгоритм $B$ выполняется за время $t A (x) 2$ на входных данных $x$ ; то есть $B$ квадратично медленнее, чем $A$ . Интуитивно, любое определение эффективности в среднем случае должно отражать идею, что $A$ эффективен в среднем тогда и только тогда, когда $B$ эффективен в среднем. Предположим, однако, что входные данные выбираются случайным образом из равномерного распределения строк длиной $n$ , и что $A$ выполняется за время $n 2$ на всех входных данных, кроме строки $1 n ,$ для которой $A$ требуется время $2 n$ . Тогда можно легко проверить, что ожидаемое время выполнения $A$ является полиномиальным, а ожидаемое время выполнения $B$ является экспоненциальным. ^[3]

Чтобы создать более надежное определение эффективности в среднем случае, имеет смысл позволить алгоритму $A$ работать дольше, чем полиномиальное время на некоторых входах, но доля входов, на которых $A$ требует все большего и большего времени выполнения, становится все меньше и меньше. Эта интуиция отражена в следующей формуле для среднего полиномиального времени выполнения, которая уравновешивает полиномиальный компромисс между временем выполнения и долей входов:

\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}

для каждого $n, t > 0$ и полинома $p$ , где $t A (x)$ обозначает время работы алгоритма $A$ на входе $x$ , а $ε$ — положительное постоянное значение. ^[6] В качестве альтернативы это можно записать как

E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C

для некоторых констант $C$ и $ε$ , где $n = | x |$ . ^[7] Другими словами, алгоритм $A$ имеет хорошую сложность в среднем случае, если после выполнения $t A (n)$ шагов, $A$ может решить все, кроме a $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠н с/( т А ( н )) ε⁠$ доля входов длины $n$ , для некоторого $ε, c > 0$ .^[3]

Проблема распределения

Следующий шаг — определить «средний» вход для конкретной проблемы. Это достигается путем связывания входов каждой проблемы с определенным распределением вероятностей. То есть, «средний случай» проблемы состоит из языка $L$ и связанного с ним распределения вероятностей $D$ , которые образуют пару $(L, D)$ . ^[7] Два наиболее распространенных класса распределений, которые разрешены, это:

Полиномиально-вычислимые распределения ( $P$ -вычислимые): это распределения, для которых можно вычислить кумулятивную плотность любого заданного входа $x$ . Более формально, если задано распределение вероятностей $μ$ и строка $x \in {0, 1} n ,$ можно вычислить значение за полиномиальное время. Это означает, что $Pr[$ $x$ $]$ также вычислимо за полиномиальное время. $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$
Распределения с полиномиальной выборкой ( $P$ -выборка): это распределения, из которых можно извлекать случайные выборки за полиномиальное время.

Эти две формулировки, хотя и похожи, не эквивалентны. Если распределение $P$ -вычислимо, оно также $P$ -выборочно, но обратное неверно, если P ≠ $P #P$ . ^[7]

AvgP и distNP

Распределительная задача $(L, D)$ находится в классе сложности $AvgP$ , если существует эффективный алгоритм среднего случая для $L$ , как определено выше. Класс $AvgP$ иногда называют $distP$ в литературе. ^[7]

Распределительная задача $(L, D)$ находится в классе сложности $distNP$ , если $L$ принадлежит $NP$ и $D$ является $P$ -вычислимым. Когда $L$ принадлежит $NP$ и $D$ является $P$ -вычислимым, $(L, D)$ принадлежит $sampNP$ . ^[7]

Вместе $AvgP$ и $distNP$ определяют усредненные аналоги $P$ и $NP$ соответственно. ^[7]

Сокращение проблем распределения

Пусть $(L, D)$ и $(L', D')$ — две распределительные задачи. $(L, D)$ в среднем сводится к $(L', D')$ (записывается как $(L, D) \leq AvgP (L', D')$ ), если существует функция $f$ , которая для каждого $n$ на входе $x$ может быть вычислена за время, полиномиальное относительно $n$ и

(Корректность) $x \in L$ тогда и только тогда, когда $f (x) \in L'$
(Доминирование) Существуют полиномы $p$ и $m$ такие, что для любых $n$ и $y$ $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

Условие доминирования усиливает представление о том, что если задача $(L, D)$ в среднем сложна, то $(L', D')$ также в среднем сложна. Интуитивно, сокращение должно предоставить способ решения экземпляра $x$ задачи $L$ путем вычисления $f (x)$ и подачи выходных данных в алгоритм, который решает $L'$ . Без условия доминирования это может быть невозможно, поскольку алгоритм, который решает $L$ за полиномиальное время в среднем, может потребовать сверхполиномиальное время на небольшом количестве входных данных, но $f$ может отобразить эти входные данные в гораздо большее множество $D' ,$ так что алгоритм $A'$ больше не будет работать за полиномиальное время в среднем. Условие доминирования позволяет таким строкам встречаться полиномиально только так часто, как в $D'$ . ^[6]

DistNP-полные задачи

$Аналогом NP$ -полноты в среднем случае является $distNP$ -полнота. Распределительная задача $(L', D')$ является $distNP$ -полной, если $(L', D')$ принадлежит $distNP$ и для каждого $(L, D)$ из $distNP$ , $(L, D)$ сводится в среднем случае к $(L', D')$ . ^[7]

Примером $distNP$ -полной задачи является ограниченная задача остановки $(BH, D)$ (для любого $P$ -вычислимого D ), определяемая следующим образом:

$BH=\{(M,x,1^{t}):M{\text{ is a non-deterministic Turing machine that accepts }}x{\text{ in}}\leq t{\text{ steps}}\}$ ^[7]

В своей оригинальной статье Левин показал пример задачи распределения мозаики, которая в среднем является $NP$ -полной. ^[5] Обзор известных $distNP$ -полных задач доступен в сети. ^[6]

Одной из областей активных исследований является поиск новых $distNP$ -полных задач. Однако поиск таких задач может быть затруднен из-за результата Гуревича, который показывает, что любая распределительная задача с плоским распределением не может быть $distNP$ -полной, если только EXP = NEXP . ^[8] (Плоское распределение $μ$ — это такое распределение, для которого существует $ε > 0$ такое, что для любого $x$ , $μ (x) \leq 2 -| x | ε$ .) Результат Ливне показывает, что все естественные $NP$ -полные задачи имеют $DistNP$ -полные версии. ^[9] Однако цель поиска естественной распределительной задачи, которая является $DistNP$ -полной, пока не достигнута. ^[10]

Приложения

Алгоритмы сортировки

Как упоминалось выше, многие ранние работы, касающиеся сложности в среднем случае, были сосредоточены на проблемах, для которых уже существовали алгоритмы полиномиального времени, такие как сортировка. Например, многие алгоритмы сортировки, использующие случайность, такие как быстрая сортировка , имеют худшее время выполнения $O(n 2)$ , но среднее время выполнения $O(n log(n))$ , где $n$ — длина сортируемого ввода. ^[2]

Криптография

Для большинства проблем анализ сложности в среднем случае проводится для поиска эффективных алгоритмов для проблемы, которая считается сложной в худшем случае. Однако в криптографических приложениях верно обратное: сложность в худшем случае не имеет значения; вместо этого мы хотим получить гарантию того, что сложность в среднем случае каждого алгоритма, который «ломает» криптографическую схему, неэффективна. ^[11]

Таким образом, все безопасные криптографические схемы полагаются на существование односторонних функций . ^[3] Хотя существование односторонних функций все еще остается открытой проблемой, многие кандидаты на роль односторонних функций основаны на сложных задачах, таких как факторизация целых чисел или вычисление дискретного журнала . Обратите внимание, что нежелательно, чтобы функция-кандидат была $NP$ -полной, поскольку это гарантировало бы только то, что в худшем случае, скорее всего, не существует эффективного алгоритма для решения задачи; на самом деле мы хотим получить гарантию того, что ни один эффективный алгоритм не сможет решить задачу на случайных входных данных (т. е. в среднем случае). Фактически, как задачи факторизации целых чисел, так и задачи дискретного журнала находятся в $NP \cap$ coNP и, следовательно, не считаются $NP$ -полными. ^[7] Тот факт, что вся криптография основана на существовании неразрешимых задач в среднем случае в $NP,$ является одной из основных мотиваций для изучения сложности в среднем случае.

Другие результаты

В 1990 году Импальяццо и Левин показали, что если существует эффективный алгоритм среднего случая для $distNP$ -полной задачи при равномерном распределении, то существует алгоритм среднего случая для каждой задачи из $NP$ при любом полиномиальном времени выборки распределения. ^[12] Применение этой теории к естественным распределительным задачам остается нерешенным открытым вопросом. ^[3]

В 1992 году Бен-Дэвид и др. показали, что если все языки в $distNP$ имеют хорошие в среднем алгоритмы принятия решений, то они также имеют хорошие в среднем алгоритмы поиска. Кроме того, они показывают, что этот вывод справедлив при более слабом предположении: если каждый язык в $NP$ в среднем прост для алгоритмов принятия решений относительно равномерного распределения, то он также в среднем прост для алгоритмов поиска относительно равномерного распределения. ^[13] Таким образом, криптографические односторонние функции могут существовать только в том случае, если существуют проблемы $distNP$ над равномерным распределением, которые в среднем сложны для алгоритмов принятия решений.

В 1993 году Фейгенбаум и Фортнау показали, что невозможно доказать при неадаптивных случайных сокращениях, что существование хорошего в среднем алгоритма для $distNP$ -полной задачи при равномерном распределении подразумевает существование эффективных алгоритмов в худшем случае для всех задач в $NP$ . ^[14] В 2003 году Богданов и Тревизан обобщили этот результат на произвольные неадаптивные сокращения. ^[15] Эти результаты показывают, что маловероятно, что можно установить какую-либо связь между сложностью в среднем случае и сложностью в худшем случае посредством сокращений. ^[3]

Смотрите также

Ссылки

↑ О. Голдрайх и С. Вадхан, Специальный выпуск о сложности в худшем и среднем случае, Comput. Complex. 16, 325–330, 2007.
^ аб Кормен, Томас Х.; Лейзерсон, Чарльз Э., Ривест, Рональд Л., Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4 .
^ abcdef А. Богданов и Л. Тревизан, «Средняя сложность», Основы и тенденции в теоретической информатике, т. 2, № 1 (2006) 1–106.
↑ Д. Кнут, Искусство программирования . Т. 3, Эддисон-Уэсли, 1973.
^ Л. Левин, «Средние полные задачи», SIAM Journal on Computing, т. 15, № 1, стр. 285–286, 1986.
^ abc J. Wang, «Теория средней вычислительной сложности», Complexity Theory Retrospective II, стр. 295–328, 1997.
^ abcdefghi С. Арора и Б. Барак, Вычислительная сложность: современный подход, Cambridge University Press, Нью-Йорк, 2009.
^ Ю. Гуревич, «Полные и неполные рандомизированные задачи NP», Труды 28-го ежегодного симпозиума по основам компьютерной науки, IEEE (1987), стр. 111–117.
^ Н. Ливне, «Все естественные NP-полные задачи имеют полные версии в среднем», Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9
^ О. Голдрайх, «Заметки о теории средней сложности Левина», Технический отчет TR97-058, Электронный коллоквиум по вычислительной сложности, 1997.
^ Дж. Кац и Й. Линделл, Введение в современную криптографию (серия «Криптография и сетевая безопасность» Чапмана и Холла/CRC), Чапман и Холл/CRC, 2007.
^ Р. Импальяццо и Л. Левин, «Нет лучших способов генерировать сложные NP-экземпляры, чем выбор случайным образом», в Трудах 31-го симпозиума IEEE по основам компьютерной науки, стр. 812–821, 1990.
^ С. Бен-Дэвид, Б. Чор , О. Голдрайх и М. Луби, «О теории средней сложности», Журнал компьютерных и системных наук, т. 44, № 2, стр. 193–219, 1992.
^ Дж. Фейгенбаум и Л. Фортноу, «Случайная самоприводимость полных множеств», SIAM Journal on Computing, т. 22, стр. 994–1005, 1993.
^ А. Богданов и Л. Тревизан, «О сведении задач NP к наихудшему случаю», в Трудах 44-го симпозиума IEEE по основам компьютерной науки, стр. 308–317, 2003.

Дальнейшее чтение

Литература по случаям средней сложности включает следующие работы:

Франко, Джон (1986), «О вероятностной производительности алгоритмов для проблемы выполнимости», Information Processing Letters , 23 (2): 103–106, doi :10.1016/0020-0190(86)90051-7.
Левин, Леонид (1986), «Средний случай полных задач», SIAM Journal on Computing , 15 (1): 285–286, doi :10.1137/0215020.
Флажоле, Филипп ; Виттер, Дж. С. (август 1987 г.), Анализ алгоритмов и структур данных в среднем случае , Tech. Отчет, Национальный институт исследований информатики и автоматизации, BP 105-78153 Le Chesnay Cedex France.
Гуревич, Юрий ; Шелах, Сахарон (1987), «Ожидаемое время вычислений для задачи о гамильтоновом пути », SIAM Journal on Computing , 16 (3): 486–502, CiteSeerX 10.1.1.359.8982 , doi : 10.1137/0216034.
Бен-Дэвид, Шай; Чор, Бенни ; Голдрайх, Одед ; Луби, Майкл (1989), «О теории средней сложности», Труды 21-го ежегодного симпозиума по теории вычислений , Ассоциация вычислительной техники , стр. 204–216.
Гуревич, Юрий (1991), «Средняя полнота случая», Журнал компьютерных и системных наук , 42 (3): 346–398, doi : 10.1016/0022-0000(91)90007-R, hdl : 2027.42/29307. См. также проект 1989 года.
Селман, Б.; Митчелл, Д.; Левек, Х. (1992), «Сложные и простые распределения задач SAT», Труды 10-й Национальной конференции по искусственному интеллекту , стр. 459–465.
Шулер, Райнер; Ямаками, Томоюки (1992), «Структурная средняя сложность случая», Proc. Основы технологий программного обеспечения и теоретической информатики , Lecture Notes in Computer Science, т. 652, Springer-Verlag, стр. 128–139.
Рейщук, Рюдигер; Шиндельхауэр, Кристиан (1993), «Точная средняя сложность случая», Труды 10-го ежегодного симпозиума по теоретическим аспектам компьютерной науки , стр. 650–661.
Венкатесан, Р.; Раджагопалан, С. (1992), «Средняя неразрешимость матричных и диофантовых задач», Труды 24-го ежегодного симпозиума по теории вычислений , Ассоциация вычислительной техники , стр. 632–642.
Кокс, Джим; Эриксон, Ларс; Мишра, Бад (1995), Средняя сложность многоуровневых силлогистик (PDF) , Технический отчет TR1995-711, Кафедра компьютерных наук Нью-Йоркского университета.
Импальяццо, Рассел (17 апреля 1995 г.), Личный взгляд на сложность среднего случая, Калифорнийский университет, Сан-Диего.
Пол Э. Блэк, «Θ», в Словаре алгоритмов и структур данных [онлайн] Пол Э. Блэк, редактор, Национальный институт стандартов и технологий США. 17 декабря 2004 г. Получено 20 февраля 2009 г.
Христос Пападимитриу (1994). Сложность вычислений. Эддисон-Уэсли.