Сложность общего случая

Сложность в общем случае — это подраздел теории сложности вычислений , который изучает сложность вычислительных задач на «большинстве входных данных».

Сложность обобщенного случая — это способ измерения сложности вычислительной задачи путем пренебрежения небольшим набором нерепрезентативных входных данных и рассмотрения сложности наихудшего случая для остальных. Малый определяется в терминах асимптотической плотности. Очевидная эффективность сложности обобщенного случая заключается в том, что для широкого спектра конкретных вычислительных задач наиболее сложные случаи кажутся редкими. Типичные случаи относительно просты.

Этот подход к сложности возник в комбинаторной теории групп , которая имеет вычислительную традицию, восходящую к началу прошлого века. Понятие общей сложности было введено в статье 2003 года ^[1] , где авторы показали, что для большого класса конечно порожденных групп общая временная сложность некоторых классических задач принятия решений из комбинаторной теории групп, а именно проблемы слов , проблемы сопряженности и проблемы членства, является линейной.

Подробное введение в общую сложность дела можно найти в обзорах. ^{[2] [3]}

Пусть I — бесконечный набор входных данных для вычислительной задачи.

Определение 1. Функция размера на I — это отображение с бесконечным диапазоном. Шар радиуса n — это .${\displaystyle \sigma :I\to \mathbb {N} }$${\displaystyle B_{n}=\{x\in I\mid \sigma (x)\leq n\}}$

Если входные данные закодированы как строки в конечном алфавите, то размер может быть длиной строки.

Пусть будет ансамблем распределений вероятностей , где — распределение вероятностей на . Если шары конечны, то каждый из них можно считать равновероятным распределением, что является наиболее распространенным случаем. Обратите внимание, что только конечное число ' могут быть пустыми или иметь ; мы их игнорируем.${\displaystyle \{\mu _{n}\}}$${\displaystyle \mu _{n}}$${\displaystyle B_{n}}$${\displaystyle B_{n}}$${\displaystyle \mu _{n}}$${\displaystyle B_{n}}$${\displaystyle \mu _{n}(B_{n})=0}$

Определение 2. Асимптотическая плотность подмножества имеет место , когда этот предел существует.${\displaystyle X\subset I}$${\displaystyle \rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})}$

Когда шары конечны и является равновероятной мерой,${\displaystyle B_{n}}$${\displaystyle \mu _{n}}$

${\displaystyle \rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.}$

В этом случае часто бывает удобно использовать сферы вместо шаров и определить . Рассуждение с использованием теоремы Штольца показывает, что существует, если существует, и в этом случае они равны.${\displaystyle I_{n}=\{x\in I\mid \sigma (x)=n\}}$${\displaystyle \rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}}$${\displaystyle \ро (X)}$${\displaystyle \rho '(X)}$

Определение 3 является общим, если и пренебрежимо малым, если . X является экспоненциально (суперполиномиально) общим, если сходимость к пределу в определении 2 является экспоненциально (суперполиномиально) быстрой, и т.д.${\displaystyle X\subseteq I}$${\displaystyle \rho (X)=1}$${\displaystyle \rho (X)=0}$

Общее подмножество X асимптотически велико. Будет ли X большим на практике, зависит от того, насколько быстро сходится к 1. Суперполиномиальная сходимость, по-видимому, достаточно быстра.${\displaystyle \mu _{n}(X\cap B_{n})}$

Определение 4 Алгоритм находится в GenP (в общем случае полиномиальное время), если он никогда не дает неверных ответов и если он дает правильные ответы за полиномиальное время на общем наборе входных данных. Проблема находится в GenP , если она допускает алгоритм в GenP . Аналогично для GenL (в общем случае линейное время ), GenE (в общем случае экспоненциальное время с линейной экспонентой), GenExp (в общем случае экспоненциальное время) и т. д. ExpGenP является подклассом GenP, для которого соответствующий общий набор является экспоненциально общим.

В более общем случае для любого мы можем определить класс Gen(f), соответствующий временной сложности O ( f ) на общем наборе входных данных.${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

Определение 5. Алгоритм решает задачу в общем случае, если он никогда не дает неверных ответов и если он дает правильные ответы на общем наборе входных данных. Задача является разрешимой в общем случае, если она решается в общем случае некоторым алгоритмом.

• Знаменитые неразрешимые проблемы : при подходящих гипотезах проблемы принятия решений о словах, сопряженности и принадлежности являются в общем случае полиномиальными. ^[1]
• Задачи поиска слов и сопряженности находятся в GenP для всех фиксированных конечно представленных групп. ^[4]

• Хорошо известная процедура перечисления смежных классов допускает вычислимую верхнюю границу для общего набора входных данных. ^[5]

• Алгоритм Уайтхеда для проверки того, отображается ли один элемент свободной группы на другой автоморфизмом, имеет экспоненциальную верхнюю границу в худшем случае, но хорошо работает на практике. Показано, что алгоритм находится в GenL . ^[6]
• Проблема сопряженности в расширениях HNN может быть неразрешимой даже для свободных групп . Однако, в общем случае, это кубическое время. ^[7]

• Проблема остановки машины Тьюринга с односторонней лентой в большинстве случаев легко разрешима; она есть в GenP ^[8]

Ситуация для двухсторонней ленты неизвестна. Однако существует своего рода нижняя граница для машин обоих типов. Проблема остановки не входит в ExpGenP ни для одной модели машины Тьюринга, ^{[9] [10]}

• Проблема почтовой корреспонденции находится в ExpGenP . ^[2]

Проблема принятия решения для арифметики Пресбургера допускает двойную экспоненциальную нижнюю границу в худшем случае ^[11] и тройную экспоненциальную верхнюю границу в худшем случае. Общая сложность неизвестна, но известно, что проблема не в ExpGenP . ^[12]

Поскольку хорошо известно, что NP-полные задачи в среднем могут быть простыми, неудивительно, что некоторые из них также являются простыми в общем случае.

• Проблема выполнимости трех находится в ExpGenP . ^[13]
• Задача о сумме подмножеств есть в GenP . ^[2]

Существует общая версия сложности односторонней функции ^[14] , которая дает тот же класс функций, но позволяет учитывать иные предположения о безопасности, чем обычно.

Серия статей ^{[15] [16] [17]} посвящена криптоанализу протокола обмена ключами Аншеля–Аншеля–Голдфельда , безопасность которого основана на предположениях о группе кос . Эта серия достигает кульминации в работе Мясникова и Ушакова (2008) ^[18] , где применяются методы из общей сложности случая для получения полного анализа атаки на основе длины и условий, при которых она работает. Общая точка зрения также предполагает разновидность новой атаки, называемой атакой на основе фактора, и более безопасную версию протокола Аншеля–Аншеля–Голдфельда.

• Известная теорема Райса утверждает, что если F является подмножеством множества частично вычислимых функций из в , то если только F или его дополнение не пусты, проблема определения того, вычисляет ли конкретная машина Тьюринга функцию из F , неразрешима. Следующая теорема дает общую версию.${\displaystyle \mathbb {N} }$${\displaystyle \{0,1\}}$

Теорема 1 ^[19] Пусть I — множество всех машин Тьюринга. Если F — подмножество множества всех частично вычислимых функций из в себя, такое, что F и его дополнение оба непусты, то проблема определения того, вычисляет ли данная машина Тьюринга функцию из F, неразрешима ни на каком экспоненциально генерическом подмножестве I.${\displaystyle \mathbb {N} }$

• Следующие теоремы взяты из: ^[1]

Теорема 2 Множество формальных языков , которые являются генерически вычислимыми, имеет меру нуль.

Теорема 3 Существует бесконечная иерархия обобщенных классов сложности. Точнее, для собственной функции сложности f , .${\displaystyle Gen(f)\subsetneq Gen(f^{3})}$

Следующая теорема показывает, что так же, как существуют проблемы среднего случая в рамках распределительных NP-задач, существуют также проблемы общего случая. Аргументы в общем случае аналогичны аргументам в среднем случае, и проблема общего случая также является проблемой среднего случая. Это проблема распределительной ограниченной остановки.

Теорема 4 ^[2] Существует понятие обобщенно-полиномиальной редукции, относительно которой распределительная ограниченная задача остановки является полной в классе распределительных NP-задач.

Мейер и Патерсон ^[20] определяют алгоритм как почти полиномиальное время, или APT, если он останавливается в пределах p(n) шагов на всех, кроме p(n) входных данных размера n . Очевидно, что алгоритмы APT включены в наш класс GenP . Мы видели несколько NP-полных задач в GenP , но Мейер и Патерсон показывают, что для APT это не так. Они доказывают, что NP-полная задача сводится к задаче в APT тогда и только тогда, когда P = NP . Таким образом, APT кажется гораздо более ограничительным, чем GenP .

Сложность общего случая похожа на сложность среднего случая . Однако есть некоторые существенные различия. Сложность общего случая является прямой мерой производительности алгоритма на большинстве входных данных, в то время как сложность среднего случая дает меру баланса между простыми и сложными примерами. Кроме того, сложность общего случая естественным образом применяется к неразрешимым проблемам .

Предположим, что есть алгоритм , временная сложность которого , в среднем полиномиальна . Какой вывод мы можем сделать о поведении на типичных входных данных?${\displaystyle {\mathcal {A}}}$${\displaystyle T:I\to \mathbb {N} }$${\displaystyle \мю}$${\displaystyle {\mathcal {A}}}$

Пример 1 Пусть I будет множеством всех слов в и определите размер как длину слова, . Определим как множество слов длины n , и предположим, что каждое является равновероятной мерой. Предположим, что T(w)=n для всех, кроме одного слова в каждом , и для исключительных слов.${\displaystyle \{0,1\}}$${\displaystyle \сигма (w)}$${\displaystyle |w|}$${\displaystyle I_{н}}$${\displaystyle \mu _{n}}$${\displaystyle I_{н}}$${\displaystyle T(w)=2^{2^{n}}}$

В этом примере T , безусловно, является полиномом на типичных входных данных, но T не является полиномом в среднем. T находится в GenP .

Пример 2 Оставьте I и как и прежде, но определите и . T является полиномом в среднем, хотя он является экспоненциальным на типичных входных данных. T не входит в GenP .${\displaystyle \sigma (w)=|w|}$${\displaystyle \mu (w)=2^{-2|w|-1}}$${\displaystyle T(w)=2^{|w|}}$

В этих двух примерах общая сложность более тесно связана с поведением на типичных входных данных, чем средняя сложность случая. Средняя сложность случая измеряет нечто другое: баланс между частотой сложных случаев и степенью сложности. ^{[21] [22]} Грубо говоря, алгоритм, который в среднем является полиномиальным по времени, может иметь только субполиномиальную долю входных данных, которые требуют суперполиномиального времени для вычисления.

Тем не менее, в некоторых случаях общая и средняя сложность случая довольно близки друг к другу. Функция является полиномиальной в -среднем на сферах, если существует такое, что где - ансамбль, индуцированный . Если f является полиномиальной в -среднем на сферах, то f является полиномиальной в -среднем, и для многих распределений справедливо обратное ^[23]${\displaystyle f:I\rightarrow \mathbb {R} ^{+}}$${\displaystyle \мю}$${\displaystyle k\geq 1}$${\displaystyle \sum _{w\in I_{n}}f^{1/k}(w)\mu _{n}(w)=O(n)}$${\displaystyle \{\mu _{n}\}}$${\displaystyle \мю}$${\displaystyle \мю}$${\displaystyle \мю}$

Теорема 5 ^[2] Если функция является полиномиальной в среднем на сферах, то f является полиномиальной относительно сферической асимптотической плотности .${\displaystyle f:I\rightarrow \mathbb {R} ^{+}}$${\displaystyle \мю}$${\displaystyle \ро '}$

Теорема 6 ^[2] Предположим, что полный алгоритм имеет субэкспоненциальное ограничение по времени T , а частичный алгоритм для той же задачи находится в ExpGenP относительно ансамбля, соответствующего вероятностной мере на входах I для . Тогда существует полный алгоритм, который имеет -среднюю временную сложность.${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle \{\mu _{n}\}}$${\displaystyle \мю}$${\displaystyle {\mathcal {A}}}$${\displaystyle \мю}$

В статье 2006 года Богданов и Тревизан вплотную подошли к определению сложности обобщенного случая. ^[24] Вместо частичных алгоритмов они рассматривают так называемые безошибочные эвристические алгоритмы. Это полные алгоритмы, которые могут потерпеть неудачу, остановившись с выводом «?». Класс AvgnegP определяется как состоящий из всех безошибочных эвристических алгоритмов A , которые работают за полиномиальное время и для которых вероятность неудачи на пренебрежимо мала, т. е. сходится суперполиномиально быстро к 0. AvgnegP является подмножеством GenP . Безошибочные эвристические алгоритмы по сути такие же, как алгоритмы с неопасными неисправностями, определенные Импальяццо, где алгоритмы с полиномиальным временем в среднем характеризуются в терминах так называемых схем неопасных алгоритмов.${\displaystyle I_{н}}$

• Сглаженный анализ — похожая концепция: измеряет наихудший случай среднего времени выполнения.