Сложность алгоритма в среднем

Первая цель — точное определение, что означает, алгоритм эффективен «в среднем». Можно попытаться определить эффективный алгоритм в среднем как алгоритм, математическое ожидание работы которого полиномиально для всех возможных входных данных. Такое определение имеет различные недостатки. В частности, это определение не устойчиво относительно изменения вычислительной модели (например, при замене многоленточной машины Тьюринга на одноленточную). Пусть, например, алгоритм A работает за время t_A(x) на входных данных x и алгоритм B работает за время t_A(x)² на входе x. То есть B квадратично медленнее A. Интуитивно ясно, что любое определение эффективности в среднем должно использовать идею, что A эффективен в среднем тогда и только тогда, когда B эффективен в среднем. Предположим, однако, что входные данные берутся случайным образом из равномерного распределенных строк длины n, и что A работает за время n² на всех входных данных, за исключением строки 1ⁿ, для которой требуется время 2ⁿ. Легко проверить, что мат. ожидание времени работы алгоритма A полиномиально, а вот мат. ожидание работы алгоритма B экспоненциально[3].

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

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

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

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

для некоторой константы C, где n = |x|[7]. Другими словами, алгоритм A имеет хорошую среднюю сложность, если после t_A(n) шагов 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 _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]}$ за полиномиальное время. Из этого следует, что Pr[x] также вычислимо за полиномиальное время.
2. Конструируемые за полиномиальное время распределения (P-конструируемое) — это распределения, для которых можно выбрать случайную выборку за полиномиальное время.

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

Задача с известными распределениями (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].

Аналогия в средней сложности для NP-сложности — это distNP-полнота. Задача с известными распределениями (L', D') является distNP-полной, если (L', D') принадлежит distNP и любая (L, D) в distNP (в средней сложности) сводима к (L', D')[7].

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

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

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

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

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

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

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