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

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

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

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

История и предыстория [ править ]

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

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

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

Определения [ править ]

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

Первая задача — точно определить, что подразумевается под алгоритмом, эффективным «в среднем». Первоначальная попытка может определить эффективный алгоритм среднего случая как алгоритм, который работает за ожидаемое полиномиальное время на всех возможных входных данных. Такое определение имеет различные недостатки; в частности, он неустойчив к изменениям в вычислительной модели. Например, предположим, что алгоритм $A$ выполняется за время $t A (x)$ на входе $x$ , а алгоритм $B$ выполняется за время $t A (x). 2$ на входе $х$ ; то есть $B$ квадратично медленнее, чем $A$ . Интуитивно понятно, что любое определение эффективности в среднем случае должно отражать идею о том, что $A$ является эффективным в среднем тогда и только тогда, когда $B$ эффективен в среднем. Предположим, однако, что входные данные выбираются случайным образом из равномерного распределения строк длиной $n$ и что $A$ выполняется за время $n. 2$ на всех входах, кроме строки $1 н$ для которого $A$ требуется время $2 н$ . Тогда можно легко проверить, что ожидаемое время работы $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 = | х |$ . ^[7] Другими словами, алгоритм $A$ имеет хорошую сложность в среднем случае, если после выполнения $t A (n)$ шагов $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} н$ можно вычислить значение $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ за полиномиальное время. Это означает, что $Pr[x]$ также вычислимо за полиномиальное время.
Распределения с выборкой за полиномиальное время ( $P$ -samplable): это распределения, из которых можно получить случайные выборки за полиномиальное время.

Эти две формулировки, хотя и похожи, но не эквивалентны. Если распределение $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', Д')$ . ^[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$ -complete доступен в Интернете. ^[6]

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

Приложения [ править ]

Алгоритмы сортировки [ править ]

Как упоминалось выше, большая часть ранних работ, касающихся сложности среднего случая, была сосредоточена на проблемах, для которых уже существовали алгоритмы с полиномиальным временем, таких как сортировка. Например, многие алгоритмы сортировки, использующие случайность, такие как Quicksort , имеют время работы в наихудшем случае $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. Сложный. 16, 325–330, 2007.
↑ Перейти обратно: Перейти обратно: ^а ^б Кормен, Томас Х.; Лейзерсон, Чарльз Э., Ривест, Рональд Л., Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж А. Богданов и Л. Тревизан, «Сложность в среднем случае», «Основы и тенденции в теоретической информатике», Vol. 2, № 1 (2006) 1–106.
^ Д. Кнут, Искусство компьютерного программирования . Том. 3, Аддисон-Уэсли, 1973 год.
↑ Перейти обратно: Перейти обратно: ^а ^б Л. Левин, «Задачи, полные в среднем случае», SIAM Journal on Computing, vol. 15, нет. 1, стр. 285–286, 1986.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Дж. Ван, «Теория вычислительной сложности в среднем случае», Ретроспектива теории сложности II, стр. 295–328, 1997.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я С. Арора и Б. Барак, Вычислительная сложность: современный подход, издательство Кембриджского университета, Нью-Йорк, Нью-Йорк, 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, vol. 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, Франция .
Гуревич Юрий ; Шела, Сахарон (1987), «Ожидаемое время вычисления для гамильтоновой задачи о пути », SIAM Journal on Computing , 16 (3): 486–502, CiteSeerX 10.1.1.359.8982 , doi : 10.1137/0216034 .
Бен-Давид, Шай; Чор, Бенни ; Гольдрейх, Одед ; Луби, Майкл (1989), «К теории средней сложности», Proc. 21-й ежегодный симпозиум по теории вычислений , Ассоциация вычислительной техники , стр. 204–216 .
Гуревич, Юрий (1991), «Средняя полнота случая», Журнал компьютерных и системных наук , 42 (3): 346–398, doi : 10.1016/0022-0000(91)90007-R , hdl : 2027.42/29307 . См. также проект 1989 года .
Селман, Б.; Митчелл, Д.; Левеск, Х. (1992), "Жесткие и простые распределения задач SAT", Proc. 10-я Национальная конференция по искусственному интеллекту , стр. 459–465 .
Шулер, Райнер; Ямаками, Томоюки (1992), «Структурная средняя сложность случая», Proc. Основы технологии программного обеспечения и теоретической информатики , Конспекты лекций по информатике, том. 652, Springer-Verlag, стр. 128–139 .
Рейщук, Рюдигер; Шиндельхауэр, Кристиан (1993), «Точная средняя сложность случая», Proc. 10-й ежегодный симпозиум по теоретическим аспектам информатики , стр. 650–661 .
Венкатесан, Р.; Раджагопалан, С. (1992), "Неразрешимость матричных и диофантовых задач в среднем случае", Proc. 24-й ежегодный симпозиум по теории вычислений , Ассоциация вычислительной техники , стр. 632–642 .
Кокс, Джим; Эриксон, Ларс; Мишра, Бад (1995), Средняя сложность многоуровневой силлогистики (PDF) , Технический отчет TR1995-711, Факультет компьютерных наук Нью-Йоркского университета .
Импальяццо, Рассел (17 апреля 1995 г.), Личный взгляд на сложность среднего случая , Калифорнийский университет, Сан-Диего .
Пол Э. Блэк, «Θ» , в Словаре алгоритмов и структур данных [онлайн] Пол Э. Блэк, изд., Национальный институт стандартов и технологий США. 17 декабря 2004 г. Проверено 20 февраля 2004 г.
Христос Пападимитриу (1994). Вычислительная сложность. Аддисон-Уэсли.

[gol07-1] О. Голдрейх и С. Вадхан, Специальный выпуск о сложности наихудшего и среднего случаев, Comput. Сложный. 16, 325–330, 2007.

[clrs-2] Перейти обратно: Перейти обратно: ^а ^б Кормен, Томас Х.; Лейзерсон, Чарльз Э., Ривест, Рональд Л., Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4 .

[bog06-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж А. Богданов и Л. Тревизан, «Сложность в среднем случае», «Основы и тенденции в теоретической информатике», Vol. 2, № 1 (2006) 1–106.

[knu73-4] Д. Кнут, Искусство компьютерного программирования . Том. 3, Аддисон-Уэсли, 1973 год.

[levin86-5] Перейти обратно: Перейти обратно: ^а ^б Л. Левин, «Задачи, полные в среднем случае», SIAM Journal on Computing, vol. 15, нет. 1, стр. 285–286, 1986.

[wangsurvey-6] Перейти обратно: Перейти обратно: ^а ^б ^с Дж. Ван, «Теория вычислительной сложности в среднем случае», Ретроспектива теории сложности II, стр. 295–328, 1997.

[ab09-7] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я С. Арора и Б. Барак, Вычислительная сложность: современный подход, издательство Кембриджского университета, Нью-Йорк, Нью-Йорк, 2009.

[gur87-8] Ю. Гуревич, "Полные и неполные рандомизированные задачи NP", Учеб. 28-й ежегодный симпозиум. на Найден. кафедры компьютерных наук, IEEE (1987), стр. 111–117.

[livne06-9] Н. Ливне, «Все естественные NP-полные задачи имеют полные версии в среднем случае», Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9

[gol97-10] О. Голдрейх, «Заметки о теории Левина о сложности среднего случая», Технический отчет TR97-058, Электронный коллоквиум по вычислительной сложности, 1997.

[katz07-11] Дж. Кац и Ю. Линделл, Введение в современную криптографию (Серия Чепмена и Холла/Crc по криптографии и сетевой безопасности), Чепмен и Холл/CRC, 2007.

[imp90-12] Р. Импальяццо и Л. Левин, «Нет лучших способов создания жестких экземпляров NP, чем равномерный случайный выбор», в материалах 31-го симпозиума IEEE по основам информатики, стр. 812–821, 1990.

[bd92-13] С. Бен-Дэвид, Б. Чор , О. Голдрейх и М. Луби, «К теории средней сложности случая», Журнал компьютерных и системных наук, том. 44, нет. 2, стр. 193–219, 1992.

[ff93-14] Дж. Фейгенбаум и Л. Фортнов, «Случайная самосократимость полных наборов», SIAM Journal on Computing, vol. 22, стр. 994–1005, 1993.

[bog03-15] А. Богданов и Л. Тревизан, «О сокращении наихудшего случая до среднего для задач NP», в материалах 44-го симпозиума IEEE по основам компьютерных наук, стр. 308–317, 2003.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]