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

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

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

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

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

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

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

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

Определения

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

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

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

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

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

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

для некоторой постоянной C, где n = | x |. Другими словами, алгоритм A имеет хорошую сложность в среднем случае, если после выполнения t _A (n) шагов A может решить все, кроме части входов длины n, для некоторого ε, c> 0. ${\ Displaystyle {\ гидроразрыва {п ^ {с}} {(т_ {А} (п)) ^ {\ эпсилон}}}}$

Проблема распределения

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

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

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

AvgP и distNP

Проблема распределения (L, D) относится к классу сложности AvgP, если существует эффективный алгоритм среднего случая для L, как определено выше. Класс AvgP иногда в литературе называется distP.

Задача распределения (L, D) относится к классу сложности distNP, если L принадлежит NP и D является P-вычислимым. Когда L находится в NP, а D является P-выборкой, (L, D) принадлежит sampNP.

Вместе AvgP и distNP определяют аналоги P и NP для среднего случая соответственно.

Сокращение между проблемами распределения

Пусть (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 '.

DistNP-Complete проблемы

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

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

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

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

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

Приложения

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

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

Криптография

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

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

Другие результаты

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

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

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

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

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

использованная литература

дальнейшее чтение

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

• Франко, Джон (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, Департамент компьютерных наук Нью-Йоркского университета.
• Импальяццо, Рассел (17 апреля 1995 г.), Персональный взгляд на сложность среднего случая , Калифорнийский университет, Сан-Диего.
• Пол Э. Блэк, «» , в Словаре алгоритмов и структур данных [онлайн] Пол Э. Блэк, изд., Национальный институт стандартов и технологий США. 17 декабря 2004 г., проверено 20 февраля 2009 г.
• Христос Пападимитриу (1994). Вычислительная сложность. Эддисон-Уэсли.