Сложность алгоритма в среднем
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае , где рассматривается максимальная сложность алгоритма по всем входным данным.
Имеются три основных причины изучения сложности в среднем[1]. Во-первых, хотя некоторые задачи могут быть трудно разрешимы в худшем случае, входные данные, которые приводят к такому поведению, на практике встречаются редко, так что сложность в среднем может оказаться более аккуратной мерой производительности алгоритма. Во-вторых, анализ сложности в среднем даёт средства и технику генерации сложных данных для задачи, что можно использовать в криптографии и дерандомизации . В-третьих, сложность в среднем позволяет выделить наиболее эффективный алгоритм на практике среди алгоритмов той же основной сложности (например, быстрая сортировка).
Анализ алгоритмов в среднем требует понятия «средних» данных алгоритма, что приводит к задаче продумывания распределения вероятностей входных данных. Может быть использован также вероятностный алгоритм. Анализ таких алгоритмов приводит к связанному понятию ожидаемой сложности[2].
История и подоплёка
Производительность алгоритмов в среднем изучалась после введения современных понятий вычислительной эффективности в 1950-х годах. Большинство начальных работ сосредотачивалось на задачах, для которых алгоритмы полиномиального в худшем случае времени были известны[3]. В 1973 Дональд Кнут[4] опубликовал третий том книги «Искусство программирования», в которой привёл широкое обозрение производительности в среднем алгоритмов для задач, которые решаются за полиномиальное время в худшем случае, такие как сортировки и вычисление медианы.
Эффективный алгоритм для NP-полных задач в общем случае предполагает, что он работает за полиномиальное время для всех входных данных, что эквивалентно сложности в худшем случае. Однако алгоритм, который неэффективен на «малом» количестве данных, может оказаться достаточно эффективным для «большинства» данных, которые встречаются на практике. Таким образом, желательно изучать свойства алгоритмов, для которых сложность в среднем может существенно отличаться от сложности в худшем случае.
Фундаментальные понятия сложности в среднем развил Левин, Леонид Анатольевич, опубликовавший в 1986 одностраничную статью [5], в которой определил сложность в среднем и полноту, приведя пример полной задачи класса distNP, аналога NP-полноты для сложности в среднем.
Определения
Эффективный в среднем алгоритм
Первая цель — точное определение, что означает, алгоритм эффективен «в среднем». Можно попытаться определить эффективный алгоритм в среднем как алгоритм, математическое ожидание работы которого полиномиально для всех возможных входных данных. Такое определение имеет различные недостатки. В частности, это определение не устойчиво относительно изменения вычислительной модели (например, при замене многоленточной машины Тьюринга на одноленточную). Пусть, например, алгоритм A работает за время tA(x) на входных данных x и алгоритм B работает за время tA(x)2 на входе x. То есть B квадратично медленнее A. Интуитивно ясно, что любое определение эффективности в среднем должно использовать идею, что A эффективен в среднем тогда и только тогда, когда B эффективен в среднем. Предположим, однако, что входные данные берутся случайным образом из равномерного распределенных строк длины n, и что A работает за время n2 на всех входных данных, за исключением строки 1n, для которой требуется время 2n. Легко проверить, что мат. ожидание времени работы алгоритма A полиномиально, а вот мат. ожидание работы алгоритма B экспоненциально[3].
Чтобы создать более прочное определение эффективности в среднем, имеет смысл позволить алгоритму A работать более чем за полиномиальное время на некоторых входных данных, но доля данных, на которых A требует всё большего и большего времени, будет становиться всё меньше и меньше. Эта идея зафиксирована в следующей формуле для среднего полиномиального времени работы, в котором сбалансированы время работы и доля входных данных:
[math]\displaystyle{ \Pr_{x \in_R D_n}[t_A(x) \geq t] \leq \frac{p(n)}{t^\epsilon} }[/math]
для любых n, t, ε > 0 и многочлена p, где tA(x) означает время работы алгоритма A на входе x[6]. Альтернативно, это можно записать следующим образом
[math]\displaystyle{ E_{x \in_R D_n}[\frac{t_{A}(x)^{\epsilon}}{n}] \leq C }[/math]
для некоторой константы C, где n = |x|[7]. Другими словами, алгоритм A имеет хорошую среднюю сложность, если после tA(n) шагов A может решить все задачи, за исключением [math]\displaystyle{ \frac{n^c}{(t_A(n))^{\epsilon}} }[/math] доли задач с длиной входа n, для некоторых ε, c > 0 [3].
Задачи с известными распределениями
Следующий шаг — определение «среднего» ввода для конкретной задачи. Это достигается путём сопоставления входу каждой задачи определённого вероятностного распределения. То есть «средняя» задача состоит из языка L (то есть набора слов, представляющих входные данные) и связанного с ним распределения D, в результате получаем пару (L, D) (задача с известными распределениями)[7]. Два наиболее распространённых класса вероятностного распределения:
- Вычислимые за полиномиальное время распределения (P-вычислимые) — это распределения, для которых можно вычислить суммарную плотность любого заданного входа x. Формально, если дано распределение μ и строка x ∈ {0, 1}n, можно вычислить значение [math]\displaystyle{ \mu(x) = \sum\limits_{y \in \{0, 1\}^n : y \leq x} \Pr[y] }[/math] за полиномиальное время. Из этого следует, что Pr[x] также вычислимо за полиномиальное время.
- Конструируемые за полиномиальное время распределения (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) ≤AvgP (L', D')), если существует функция f, такая, что для любого n её можно вычислить при входе x за полиномиальное от n время и
- (Корректность) x ∈ L тогда и только тогда, когда f(x) ∈ L'
- (Доминирование) Существуют многочлены p и m, такие, что для любого n и y, [math]\displaystyle{ \sum\limits_{x: f(x) = y} D_n(x) \leq p(n)D'_{m(n)}(y) }[/math]
Условие доминирования приводит к идее, что если задача (L, D) сложна в среднем, то (L', D') также сложна в среднем. Интуитивно, сведение должно обеспечивать путь к решению задачи L для входа x путём вычисления f(x) и передать выход алгоритма в алгоритм, который решает L'. Без условия доминирования это может оказаться невозможным, поскольку алгоритм, решающий L за полиномиальное время в среднем, может работать за суперполиномиальное время для малого числа входов, но эти входы могут отображаться в большое множество в D', так что алгоритм A' в среднем за полиномиальное время работать не будет. Условие доминирования определяет, что такие строки будут случаться в D' полиномиально часто[6].
DistNP-полные задачи
Аналогия в средней сложности для NP-сложности — это distNP-полнота. Задача с известными распределениями (L', D') является distNP-полной, если (L', D') принадлежит distNP и любая (L, D) в distNP (в средней сложности) сводима к (L', D')[7].
Примером distNP-полной задачи служит ограниченная задача остановки, BH, определяемая следующим образом:
BH = {(M,x,1t) : M — недетерминированная машина Тьюринга, которая принимает x за ≤ t шагов[7].
В своей статье Левин показал пример задачи замощения, которая NP-полна в среднем[5]. Обзор известных distNP-полных задач можно найти в книге Ванга[6].
Ведутся активные исследования в поиске новых distNP-полных задач. Однако поиск таких задач может быть трудным ввиду результата Гуревича, который показал, что любая задача с известными распределениями не может быть distNP-полной, если не EXP = NEXP[8]. (Равномерное распределение μ — одно из распределений, для которого существует ε > 0, такое, что для любого x μ(x) ≤ 2-|x|ε.) Результат Ливне показывает, что все естественные NP задачи имеют DistNP-полную версию [9]. Однако цель поиска естественных распределительных задач, являющихся DistNP-полными, не достигнута[10].
Приложения
Алгоритмы сортировки
Как упоминалось выше, много ранних работ по сложности в среднем фокусировались на задачах, для которых алгоритмы полиномиального времени были известны, такие как сортировка. Например, многие алгоритмы сортировки, такие как быстрая сортировка, имеют время работы в худшем случае O(n2), но время работы в среднем 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].
См. также
Примечания
- ↑ Goldreich, Vadhan, 2007, с. 325–330.
- ↑ Cormen, Leiserson, Rivest, Stein, 2009, с. 28.
- ↑ 3,0 3,1 3,2 3,3 3,4 3,5 Bogdanov, Trevisan, 2006, с. 1–106.
- ↑ Knuth, 1973.
- ↑ 5,0 5,1 Levin, 1986, с. 285–286.
- ↑ 6,0 6,1 6,2 Wang, 1997, с. 295–328.
- ↑ 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8 Arora, Barak, 2009.
- ↑ Gurevich, 1987, с. 111–117.
- ↑ Livne, 2006.
- ↑ Goldreich, 1997.
- ↑ Cormen, Leiserson, Rivest, Stein, 2009.
- ↑ Katz, Lindell, 2007.
- ↑ Impagliazzo, Levin, 1990, с. 812–821.
- ↑ Ben-David, Chor, Goldreich, Luby, 1992, с. 193–219.
- ↑ Feigenbaum, Fortnow, 1993, с. 994–1005.
- ↑ Bogdanov, Trevisan, 2003, с. 308–317.
Литература
- 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.
Для улучшения этой статьи желательно: |