Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Анализ среднего случая требует понятия «среднего» входа в алгоритм, что приводит к проблеме разработки распределения вероятностей по входам. В качестве альтернативы можно использовать рандомизированный алгоритм . Анализ таких алгоритмов приводит к связанному с ними понятию ожидаемой сложности . [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 эффективен в среднем. Однако предположим, что входные данные берутся случайным образом из равномерного распределения строк с длиной, и что A выполняется за время n 2 на всех входах, кроме строки 1 n, для которой A требуется время 2 n . Тогда можно легко проверить, что ожидаемое время работы A является полиномиальным, но ожидаемое время работы B экспоненциально. [3]

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

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

для некоторой постоянной C, где n = | x |. [7] Другими словами, алгоритм A имеет хорошую сложность в среднем случае, если после выполнения t A (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') также в среднем трудна. Интуитивно сокращение должно обеспечивать способ решения экземпляра x задачи L путем вычисления f (x) и передачи выходных данных алгоритму, который решает L '. Без условия доминирования это может быть невозможно, так как алгоритм, который решает L в среднем за полиномиальное время, может занимать сверхполиномиальное время на небольшом количестве входов, но f может отображать эти входы в гораздо больший набор D ', так что алгоритм A 'больше не работает в среднем за полиномиальное время. Условие доминирования только позволяет таким строкам встречаться полиномиально, как это часто бывает в D '. [6]

DistNP-Complete проблемы [ править ]

Средним случаем аналогом NP-полноты является distNP-полнота. Проблема распределения (L ', D') является distNP-полной, если (L ', D') находится в distNP и для каждого (L, D) в distNP, (L, D) в среднем сводится к (L ' , D '). [7]

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

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

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

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

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

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

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

Криптография [ править ]

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

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

Другие результаты [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ О. Голдрайх и С. Вадхан, Специальный выпуск о наихудшем и среднем сложностях, Comput. Сложный. 16, 325–330, 2007.
  2. ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э., Ривест, Рональд Л., Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03384-4 .
  3. ^ a b c d e f А. Богданов и Л. Тревизан, "Сложность среднего случая", Основы и тенденции теоретической информатики, Vol. 2, № 1 (2006) 1–106.
  4. ^ Д. Кнут, Искусство программирования . Vol. 3, Аддисон-Уэсли, 1973.
  5. ^ a b Л. Левин, "Полные задачи среднего случая", SIAM Journal on Computing, vol. 15, вып. 1. С. 285–286, 1986.
  6. ^ a b c Дж. Ван, "Теория вычислительной сложности в среднем случае", Ретроспектива теории сложности II, стр. 295–328, 1997.
  7. ^ a b c d e f g h i С. Арора и Б. Барак, Вычислительная сложность: современный подход, Cambridge University Press, Нью-Йорк, Нью-Йорк, 2009.
  8. ^ Ю. Гуревич, "Полные и неполные рандомизированные задачи NP", Proc. 28-й ежегодный симпозиум. на Найдено. компьютерных наук, IEEE (1987), стр. 111–117.
  9. ^ Н. Ливне, "Все естественные NP-полные задачи имеют полные версии в среднем случае", Вычислительная сложность (2010) 19: 477. https://doi.org/10.1007/s00037-010-0298-9
  10. ^ О. Голдрайх, "Заметки по теории сложности среднего случая Левина", Технический отчет TR97-058, Электронный коллоквиум по вычислительной сложности, 1997.
  11. ^ Дж. Кац и Ю. Линделл, Введение в современную криптографию (серия Chapman and Hall / Crc Cryptography and Network Security Series), Chapman and Hall / CRC, 2007.
  12. ^ Р. Импальяццо и Л. Левин, «Нет лучших способов генерировать жесткие экземпляры NP, чем выбор случайным образом равномерно», в материалах 31-го симпозиума IEEE по основам информатики, стр. 812–821, 1990.
  13. ^ С. Бен-Дэвид, Б. Чор, О. Голдрейх и М. Люби, "К теории средней сложности случая", Журнал компьютерных и системных наук, вып. 44, нет. 2. С. 193–219, 1992.
  14. ^ Дж. Фейгенбаум и Л. Фортноу, "Самосокращение случайных полных наборов", SIAM Journal on Computing, vol. 22. С. 994–1005, 1993.
  15. ↑ А. Богданов и Л. Тревизан, «О сокращении от худшего случая к среднему для проблем NP», в материалах 44-го симпозиума IEEE по основам информатики, стр. 308–317, 2003.

Дальнейшее чтение [ править ]

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

  • Франко, Джон (1986), "О вероятностной производительности алгоритмов для задачи выполнимости", Information Processing Letters , 23 (2): 103-106, DOI : 10,1016 / 0020-0190 (86) 90051-7.
  • Левин, Леонид (1986), "усредненный полные проблемы", SIAM журнал по вычислениям , 15 (1): 285-286, DOI : 10,1137 / 0215020.
  • Флажолет, Филипп ; Виттер, JS (август 1987 г.), Анализ среднего случая алгоритмов и структур данных , Tech. Отчет, Institut National de Recherche en Informatique et en Automatique, BP 105-78153 Le Chesnay Cedex France.
  • Гуревич, Юрий ; Сала, Saharon (1987), "Ожидаемое время вычисления для гамильтоновой задачи пути ", SIAM журнал по вычислениям , 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 , ЛВП : 2027,42 / 29307. Смотрите также 1989 проект .
  • Selman, B .; Mitchell, D .; Левеск, Х. (1992), "Жесткие и простые распределения задач SAT", Proc. 10-я Национальная конференция по искусственному интеллекту , стр. 459–465..
  • Шулер, Райнер; Ямаками, Томоюки (1992), "Структурная средняя сложность случая", Proc. Основы программных технологий и теоретической информатики , Конспект лекций по информатике, 652 , Springer-Verlag, стр. 128–139..
  • Рейщук, Рюдигер; Шиндельхауэр, Кристиан (1993), "Точная средняя сложность случая", Proc. 10-й ежегодный симпозиум по теоретическим аспектам информатики , стр. 650–661..
  • Venkatesan, R .; Раджагопалан, С. (1992), "Средний случай неразрешимости матричных и диофантовых проблем", Proc. 24-й ежегодный симпозиум по теории вычислений , Ассоциация вычислительной техники , стр. 632–642..
  • Кокс, Джим; Эриксон, Ларс; Мишра, Бад (1995), Средняя сложность случая многоуровневой силлогистики (PDF) , Технический отчет TR1995-711, Департамент компьютерных наук Нью-Йоркского университета.
  • Impagliazzo, Рассел (17 апреля 1995 г.), Персональный взгляд на сложность среднего случая , Калифорнийский университет, Сан-Диего.
  • Пол Э. Блэк, «» , в Словаре алгоритмов и структур данных [онлайн] Пол Э. Блэк, изд., Национальный институт стандартов и технологий США. 17 декабря 2004 г., проверено 20 февраля 2009 г.
  • Христос Пападимитриу (1994). Вычислительная сложность. Эддисон-Уэсли.