WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

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

Анализ алгоритмов в среднем требует понятия «средних» данных алгоритма, что приводит к задаче продумывания распределения вероятностей входных данных. Может быть использован также вероятностный алгоритм. Анализ таких алгоритмов приводит к связанному понятию ожидаемой сложности[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 требует всё большего и большего времени, будет становиться всё меньше и меньше. Эта идея зафиксирована в следующей формуле для среднего полиномиального времени работы, в котором сбалансированы время работы и доля входных данных:

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

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

Задачи с известными распределениями

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

  1. Вычислимые за полиномиальное время распределения (P-вычислимые) — это распределения, для которых можно вычислить суммарную плотность любого заданного входа x. Формально, если дано распределение μ и строка x ∈ {0, 1}n, можно вычислить значение за полиномиальное время. Из этого следует, что Pr[x] также вычислимо за полиномиальное время.
  2. Конструируемые за полиномиальное время распределения (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 время и

  1. (Корректность) x ∈ L тогда и только тогда, когда f(x) ∈ L'
  2. (Доминирование) Существуют многочлены p и m, такие, что для любого n и y,

Условие доминирования приводит к идее, что если задача (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[en][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].

См. также

Примечания

Литература

  • 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.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии