Общая сложность - Generic-case complexity

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

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

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

Подробное описание общей сложности кейсов можно найти в опросах.^[2][3]

Основные определения

Асимптотическая плотность

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

Определение 1. Функция размера на я это карта ${\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 \rho (X)}$существует если ${\displaystyle \rho '(X)}$ делает, и в этом случае они равны.

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

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

Классы общей сложности

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

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

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

Теория и приложения

Комбинаторные задачи теории групп

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

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

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

• Проблема сопряженности в Расширения HNN может быть неразрешимым даже для бесплатные группы. Однако обычно это кубическое время.^[7]

Проблема остановки и проблема почтовой корреспонденции

• В проблема остановки для Машина Тьюринга с односторонним скотчем в большинстве случаев легко разрешима; он находится в GenP^[8]

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

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

Арифметика пресбургера

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

NP полные задачи

Как известно, NP-полные задачи в среднем могут быть легкими, неудивительно, что некоторые из них в целом также просты.

• Три проблема выполнимости в ExpGenP.^[13]
• В проблема суммы подмножества в GenP.^[2]

Односторонние функции

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

Криптография с открытым ключом

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

Список общих теоретических результатов

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

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

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

Теорема 2. Набор формальные языки которые в общем случае вычислимы, имеют нулевую меру.

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

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

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

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

Сравнение с предыдущей работой

Почти полиномиальное время

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

Средняя сложность

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

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

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

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

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

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

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

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

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

Безошибочные эвристические алгоритмы

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

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

1. И. Капович, А. Мясников, П. Шупп, В. Шпильрайн, Общая сложность случая, проблемы принятия решений в теории групп и случайные блуждания, J. Алгебра, том 264 (2003), 665–694.
2. Гильман Р., Мясников А.Г., Мясников А.Д., Ушаков А. Общая сложность дела, неопубликованный первый черновик книги, 143 стр.
3. Гильман Р., Мясников А.Г., Мясников А.Д., Ушаков А. Отчет об общей сложности случая, Вестник Омского университета, Спецвыпуск, 2007, 103–110.
4. А. Ушаков, Диссертация, Городской университет Нью-Йорка, 2005 г.
5. Р. Гилман, Трудные проблемы теории групп, доклад на Международной конференции по геометрическим и комбинаторным методам в теории групп и теории полугрупп, 18 мая 2009 г.
6. И. Капович, П. Шупп, В. Шпильрайн, Общие свойства алгоритма Уайтхеда и жесткость изоморфизма случайных групп с одним соотношением, Pacific J. Math. 223 (2006)
7. СРЕДНИЙ. Боровик, А.Г. Мясников, В. Ремесленников, Общая сложность проблемы сопряженности в HNN-расширениях и алгоритмическая стратификация групп Миллера, Междунар. J. Algebra Comput. 17 (2007), 963–997.
8. Дж. Д. Хэмкинс и А. Мясников, Проблема остановки разрешима на множестве с асимптотической вероятностью единица., Нотр-Дам Дж. Формальная логика 47 (2006), 515–524.
9. А. Мясников и А. Рыбалов, Общая сложность неразрешимых проблем, Журнал символической логики 73 (2008), 656–673.
10. А. Рыбалов, О сильно общей неразрешимости проблемы остановки, Теорет. Comput. Sci. 377 (2007), 268–270.
11. М. Дж. Фишер и М. О. Рабин, Сверхэкспоненциальная сложность арифметики Пресбургера, Труды симпозиума SIAM-AMS по прикладной математике 7 (1974) 2741.
12. А. Рыбалов, Общая сложность арифметики Пресбургера, 356–361 во Втором международном симпозиуме по компьютерным наукам в России, CSR 2007, Lecture Notes in Computer Science 4649, Springer 2007.
13. Гильман Р., Мясников А. Г., Мясников А. Д., Ушаков А. Отчет о сложности общего случая, Вестник Омского университета, Специальный выпуск, 2007, 103–110.
14. А. Д. Мясников, Общая сложность и односторонние функции, Группы, сложность и криптография, 1, (2009), 13–31.
15. Гильман Р., Мясников А.Г., Мясников А.Д., Ушаков А. Новые разработки в коммутаторном обмене ключами, Proc. Первый Int. Конф. по символическим вычислениям и криптографии (SCC-2008), Пекин, 2008 г.
16. А. Г. Мясников, В. Шпильрайн, А. Ушаков, Практическая атака на криптографический протокол на основе группы кос, in Lecture Notes in Computer Science, 3621, Springer Verlag, 2005, 86–96.
17. А. Д. Мясников, А. Ушаков, Атака на основе длины и группы кос: криптоанализ протокола обмена ключами Аншеля – Аншеля – Голдфельда, в Криптографии с открытым ключом PKC 2007, 76–88, Lecture Notes in Comput. Sci., 4450, Springer, Берлин, 2007.
18. А. Г. Мясников, А. Ушаков, Случайные подгруппы и анализ атак на основе длины и фактора, Журнал математической криптологии, 2 (2008), 29–61.
19. А. Мясников и А. Рыбалов, Общая сложность неразрешимых проблем, Журнал символической логики 73 (2008), 656–673.
20. А. Р. Мейер и М. С. Патерсон, С какой периодичностью кажутся неразрешимымипроблемы сложные?, M.I.T. Технический отчет, MIT / LCS / TM-126, февраль 1979 г.
21. Ю. Гуревич, Игра претендент-решатель: вариации на тему P =? NP, Logicin Computer Science Column, The Bulletin of the EATCS, October 1989, p.112-121.
22. Р. Импальяццо, Личный взгляд на сложность среднего случая, в материалах 10-й ежегодной конференции по теории сложности - SCT 1995, IEEE ComputerSociety, 1995, стр. 134.
23. Ю. Гуревич, Средняя полнота кейса, Журнал компьютерных и системных наук, 42 (1991), 346–398.
24. А. Богданов, Л. Тревизан, Средняя сложность, Найденный. Trends Theor. Comput. Sci. 2, №1, 111 с. (2006) ..