Сложность алгоритма в среднем

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

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

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

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

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

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

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

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

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

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

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

для некоторой константы C, где n = |x|^[7]. Другими словами, алгоритм A имеет хорошую среднюю сложность, если после t_A(n) шагов A может решить все задачи, за исключением ${\displaystyle {\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}}$ доли задач с длиной входа n, для некоторых ε, c > 0 ^[3].

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

1. Вычислимые за полиномиальное время распределения (P-вычислимые) — это распределения, для которых можно вычислить суммарную плотность любого заданного входа x. Формально, если дано распределение μ и строка x ∈ {0, 1}ⁿ, можно вычислить значение ${\displaystyle \mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]}$ за полиномиальное время. Из этого следует, что Pr[x] также вычислимо за полиномиальное время.
2. Конструируемые за полиномиальное время распределения (P-конструируемое) — это распределения, для которых можно выбрать случайную выборку за полиномиальное время.

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

Задача с известными распределениями (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) ≤_AvgP (L', D')), если существует функция f, такая, что для любого n её можно вычислить при входе x за полиномиальное от n время и

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

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

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

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

BH = {(M,x,1^t) : M — недетерминированная машина Тьюринга, которая принимает x за ≤ t шагов^[7].

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

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

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

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

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

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

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

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

• Вероятностный анализ алгоритмов^[англ.]
• NP-полная задача
• Сложность в худшем случае^[англ.]

• S. Arora, B. Barak. Computational Complexity: A Modern Approach. — New York, NY: Cambridge University Press, 2009.
• S. Ben-David, B. Chor, O. Goldreich, M. Luby. On the theory of average case complexity // Journal of Computer and System Sciences. — 1992. — Т. 44, вып. 2.
• A. Bogdanov, L. Trevisan. Proceedings of the 44th IEEE Symposium on Foundations of Computer Science. — 2003.
• A. Bogdanov, L. Trevisan. Average-Case Complexity // Foundations and Trends in Theoretical Computer Science. — 2006. — Т. 2, вып. 1. — С. 1–106.
• R. Impagliazzo, L. Levin. No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random // Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. — 1990.
• J. Feigenbaum, L. Fortnow. Random-self-reducibility of complete sets // SIAM Journal on Computing. — 1993. — Т. 22.
• J. Katz, Y. Lindell. Introduction to Modern Cryptography. — Chapman and Hall/CRC, 2007. — (Chapman and Hall/Crc Cryptography and Network Security Series).
• D. Knuth. The Art of Computer Programming. — Addison-Wesley, 1973. — Т. 3.
• L. Levin. Average case complete problems // SIAM Journal on Computing. — 1986. — Т. 15, вып. 1.
• N. Livne. All Natural NPC Problems Have Average-Case Complete Versions. — 2006.
• J. Wang. Complexity Theory Retrospective II. — 1997.
• Y. Gurevich. Complete and incomplete randomized NP problems // Proc. 28th Annual Symp. on Found. of Computer Science, IEEE. — 1987.
• O. Goldreich. Notes on Levin's theory of average-case complexity // Technical Report TR97-058, Electronic Colloquium on Computational Complexity. — 1997.
• O. Goldreich, S. Vadhan. Special issue on worst-case versus average-case complexity // Comput. Complex. — 2007. — Вып. 16.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (3rd ed.) [1990].. — MIT Press and McGraw-Hill., 2009. — ISBN 0-262-03384-4.

• John Franco. On the probabilistic performance of algorithms for the satisfiability problem // Information Processing Letters. — 1986. — Т. 23, вып. 2. — С. 103–106. — doi:10.1016/0020-0190(86)90051-7.
• Leonid Levin. Average case complete problems // SIAM Journal on Computing. — 1986. — Т. 15, вып. 1. — С. 285–286. — doi:10.1137/0215020.
• Philippe Flajolet, J. S. Vitter. Average-case analysis of algorithms and data structures. — Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France, 1987. — (Tech. Report).
• Yuri Gurevich, Saharon Shelah. Expected computation time for Hamiltonian path problem // SIAM Journal on Computing. — 1987. — Т. 16, вып. 3. — С. 486–502. — doi:10.1137/0216034.
• Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby. Proc. 21st Annual Symposium on Theory of Computing. — Association for Computing Machinery, 1989. — С. 204–216.
• Yuri Gurevich. Average case completeness // Journal of Computer and`System Sciences. — 1991. — Т. 42, вып. 3. — С. 346–398. — doi:10.1016/0022-0000(91)90007-R.. См. также 1989 draft.
• B. Selman, D. Mitchell, H. Levesque. Proc. 10th National Conference on Artificial Intelligence. — 1992. — С. 459–465.
• Rainer Schuler, Tomoyuki Yamakami. Proc. Foundations of Software Technology and Theoretical Computer Science. — Springer-Verlag, 1992. — Т. 652. — С. 128–139. — (Lecture Notes in Computer Science).
• Rüdiger Reischuk, Christian Schindelhauer. Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science. — 1993. — С. 650–661.
• R. Venkatesan, S. Rajagopalan. Proc. 24th Annual Symposium on Theory of Computing. — Association for Computing Machinery, 1992. — С. 632–642.
• Jim Cox, Lars Ericson, Bud Mishra. The average case complexity of multilevel syllogistic. — New York University Computer Science Department, 1995.
• Russell Impagliazzo. A personal view of average-case complexity. — University of California, San Diego, 1995.
• Paul E. Black, «Θ», in Dictionary of Algorithms and Data Structures[online]Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
• Christos Papadimitriou. Computational Complexity. — Addison-Wesley, 1994.