Средняя сложность - Average-case complexity

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

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

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

История и предыстория

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

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

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

Определения

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

Первая задача - точно определить, что подразумевается под алгоритмом, который эффективен «в среднем». Первоначальная попытка может определить эффективный алгоритм среднего случая как алгоритм, который выполняется за ожидаемое полиномиальное время по всем возможным входам. У такого определения есть различные недостатки; в частности, он не устойчив к изменениям в вычислительной модели. Например, предположим, что алгоритм A работает за время t_А(x) на входе x и алгоритм B работает за время t_А(Икс)² на входе x; то есть B квадратично медленнее, чем A. Интуитивно, любое определение эффективности в среднем случае должно отражать идею о том, что A эффективен в среднем тогда и только тогда, когда B эффективен в среднем. Однако предположим, что входные данные берутся случайным образом из равномерного распределения строк с длиной ${displaystyle n}$, и что A бежит за время n² на всех входах, кроме строки 1^п для которого A занимает время 2^п. Тогда можно легко проверить, что ожидаемое время работы A является полиномиальным, но ожидаемое время работы B экспоненциально.^[3]

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

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

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

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

для некоторой постоянной C, где n = | x |.^[7] Другими словами, алгоритм A имеет хорошую сложность в среднем случае, если после выполнения t_А(n) шагов, A может решить все, кроме 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 _{yin {0,1}^{n}:yleq x}Pr[y]}$ за полиномиальное время. Отсюда следует, что Pr [x] также вычислим за полиномиальное время.
2. Распределения с выборкой за полиномиальное время (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 ${displaystyle 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-Complete проблемы

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

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

ВН = {(М, х, 1^т): 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]

Приложения

Алгоритмы сортировки

Как упоминалось выше, большая часть ранних работ, связанных со сложностью среднего случая, была сосредоточена на задачах, для которых уже существовали алгоритмы с полиномиальным временем, таких как сортировка. Например, многие алгоритмы сортировки, использующие случайность, такие как Быстрая сортировка, имеют время работы в худшем случае O (n²), но среднее время выполнения 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-полной задачи при равномерном распределении подразумевает существование наихудшего случая. эффективные алгоритмы решения всех задач в НП.^[14] В 2003 году Богданов и Тревизан обобщили этот результат на произвольные неадаптивные редукции.^[15] Эти результаты показывают, что маловероятно, что какая-либо связь между сложностью среднего и наихудшим случаем может быть установлена ​​посредством редукций.^[3]

Смотрите также

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

Рекомендации

1. О. Голдрейх и С. Вадхан, Специальный выпуск о наихудшем и среднем сложностях, Comput. Сложный. 16, 325–330, 2007.
2. Cormen, Thomas H .; Лейзерсон, Чарльз Э., Ривест, Рональд Л., Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03384-4.
3. А. Богданов и Л. Тревизан, "Сложность среднего случая", Основы и тенденции теоретической информатики, Vol. 2, № 1 (2006) 1–106.
4. Д. Кнут, Искусство программирования. Vol. 3, Аддисон-Уэсли, 1973.
5. Л. Левин, "Полные задачи среднего случая", SIAM Journal on Computing, vol. 15, нет. 1. С. 285–286, 1986.
6. Дж. Ван, "Теория сложности вычислений в среднем случае", Ретроспектива теории сложности II, стр. 295–328, 1997.
7. С. Арора и Б. Барак, Вычислительная сложность: современный подход, Издательство Кембриджского университета, Нью-Йорк, Нью-Йорк, 2009.
8. Ю. Гуревич, "Полные и неполные рандомизированные NP-задачи", Тр. 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), "О вероятностной производительности алгоритмов для проблемы выполнимости", Письма об обработке информации, 23 (2): 103–106, Дои:10.1016/0020-0190(86)90051-7.
• Левин Леонид (1986), "Полные задачи среднего случая", SIAM Журнал по вычислениям, 15 (1): 285–286, Дои:10.1137/0215020.
• Флажоле, Филипп; Виттер, Дж. С. (Август 1987 г.), Средний случай анализа алгоритмов и структур данных, Тех. Отчет Национального института научных исследований в области информатики и автоматизации, Б.П. 105-78153 Le Chesnay Cedex France.
• Гуревич Юрий; Шела, Сахарон (1987), «Ожидаемое время вычисления для Гамильтонова проблема пути ", SIAM Журнал по вычислениям, 16 (3): 486–502, CiteSeerX  10.1.1.359.8982, Дои:10.1137/0216034.
• Бен-Давид, Шай; Чор, Бенни; Гольдрайх, Одед; Луби, Майкл (1989), "К теории средней сложности случая", Proc. 21-й ежегодный симпозиум по теории вычислений, Ассоциация вычислительной техники, стр. 204–216.
• Гуревич Юрий (1991), «Средняя полнота случая», Журнал компьютерных и системных наук, 42 (3): 346–398, Дои:10.1016 / 0022-0000 (91) 90007-Р, HDL: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, Департамент компьютерных наук Нью-Йоркского университета.
• Импальяццо, Рассел (17 апреля 1995 г.), Личный взгляд на сложность среднего случая, Калифорнийский университет в Сан-Диего.
• Пол Э. Блэк, "Θ", в Словаре алгоритмов и структур данных [онлайн] Пол Э. Блэк, редактор Национального института стандартов и технологий США. 17 декабря 2004. Проверено 20 февраля 2009.
• Христос Пападимитриу (1994). Вычислительная сложность. Эддисон-Уэсли.