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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общие классы сложности

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

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

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

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

Задачи комбинаторной теории групп

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

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

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

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

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

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

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

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

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

НП полные проблемы

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

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

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

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

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

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

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

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

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

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

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

Теорема 3. Существует бесконечная иерархия общих классов сложности. Точнее, для правильной функции сложности f , $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 .

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Перейти обратно: ^а ^б ^с И. Капович, А. Мясников, П. Шупп и В. Шпильрайн, Общая сложность случая, проблемы принятия решений в теории групп и случайных блужданиях , Журнал Алгебра, том 264 (2003), 665–694.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Общая сложность случая , неопубликованный первый вариант книги, 143 страницы.
^ Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Отчет о сложности общего случая , Вестник Омского университета, специальный выпуск, 2007, 103–110.
^ А. Ушаков, Диссертация , Городской университет Нью-Йорка, 2005.
^ Р. Гилман, Сложные проблемы теории групп , доклад на Международной конференции.по геометрическим и комбинаторным методам в теории групп и теории полугрупп,18 мая 2009 г.
^ И. Капович, П. Шупп, В. Шпильрайн, Общие свойства алгоритма Уайтхеда и жесткость изоморфизма случайных групп с одним соотношением , Pacific J. Math. 223 (2006)
^ А. В. Боровик, А. Г. Мясников, В. Н. Ремесленников, Общая сложность проблемы сопряженности в HNN-расширениях и алгоритмическая стратификация групп Миллера ,Интерн. Дж. Алгебра Компьютер. 17 (2007), 963–997.
^ Дж. Д. Хамкинс и А. Мясников, Проблема остановки разрешима на множестве асимптотической вероятности один , Notre Dame J. Formal Logic 47 (2006), 515–524.
^ А. Мясников и А. Рыбалов, Общая сложность неразрешимых задач , Журнал символической логики 73 (2008), 656–673.
^ А. Рыбалов, О сильно генерической неразрешимости проблемы остановки , Теор. Вычислить. наук. 377 (2007), 268–270.
^ М. Дж. Фишер и М. О. Рабин, Суперэкспоненциальная сложность арифметики Пресбургера , Труды симпозиума SIAM-AMS по прикладной математике 7 (1974) 2741.
^ А. Рыбалов, Общая сложность арифметики Пресбургера , 356–361, Второй международный симпозиум по информатике в России, CSR 2007, Конспекты лекций по информатике 4649, Springer 2007.
^ Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Отчет о дженериках.Сложность случая, Вестник Омского университета, Спецвыпуск, 2007, 103–110.
^ А.Д. Мясников, Общая сложность и односторонние функции , Группы, сложность и криптография, 1, (2009), 13–31.
^ Р. Гилман, А. Г. Мясников, А. Д. Мясников, А. Ушаков, Новые разработки в области обмена ключами коммутаторов , Учеб. Первый межд. Конф. по символическим вычислениям и криптографии (SCC-2008), Пекин, 2008 г.
^ А. Г. Мясников, В. Шпильрайн, А. Ушаков, Практическая атака на криптографический протокол на основе группы кос , в конспектах лекций по информатике, 3621, Springer Verlag,2005, 86–96.
^ А.Д. Мясников и А. Ушаков, Группы атак и кос на основе длины: криптоанализ протокола обмена ключами Аншеля-Аншеля-Гольдфельда , в Криптография с открытым ключом PKC 2007, 76–88, Конспекты лекций по вычислениям. Sci., 4450, Шпрингер, Берлин, 2007.
^ А. Г. Мясников и А. Ушаков, Случайные подгруппы и анализ атак на основе длины и факторизации , Журнал математической криптологии, 2 (2008), 29–61.
^ А. Мясников и А. Рыбалов, Общая сложность неразрешимых задач , Журнал символической логики 73 (2008), 656–673.
^ А. Р. Мейер и М. С. Патерсон, С какой частотой кажутся трудными неразрешимые проблемы? , Технический отчет MIT, MIT/LCS/TM-126, февраль 1979 г.
^ Ю. Гуревич, Игра «Челленджер-решатель»: вариации на тему P =?NP , Колонка «Логика в информатике», Бюллетень EATCS, октябрь 1989 г., стр. 112-121.
^ Р. Импальяццо, Личный взгляд на сложность в среднем случае , в материалах 10-й ежегодной конференции по теории структуры сложности - SCT 1995, Компьютерное общество IEEE, 1995, стр. 134.
^ Ю. Гуревич, Средняя полнота случая , Журнал компьютерных и системных наук, 42(1991), 346–398.
^ А. Богданов, Л. Тревизан, Средняя сложность , Найдено. Теория тенденций. Вычислить. наук. 2 , № 1, 111 с. (2006).

[KMSS-1] Перейти обратно: ^а ^б ^с И. Капович, А. Мясников, П. Шупп и В. Шпильрайн, Общая сложность случая, проблемы принятия решений в теории групп и случайных блужданиях , Журнал Алгебра, том 264 (2003), 665–694.

[GMMU-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Общая сложность случая , неопубликованный первый вариант книги, 143 страницы.

[3] Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Отчет о сложности общего случая , Вестник Омского университета, специальный выпуск, 2007, 103–110.

[4] А. Ушаков, Диссертация , Городской университет Нью-Йорка, 2005.

[5] Р. Гилман, Сложные проблемы теории групп , доклад на Международной конференции.по геометрическим и комбинаторным методам в теории групп и теории полугрупп,18 мая 2009 г.

[6] И. Капович, П. Шупп, В. Шпильрайн, Общие свойства алгоритма Уайтхеда и жесткость изоморфизма случайных групп с одним соотношением , Pacific J. Math. 223 (2006)

[7] А. В. Боровик, А. Г. Мясников, В. Н. Ремесленников, Общая сложность проблемы сопряженности в HNN-расширениях и алгоритмическая стратификация групп Миллера ,Интерн. Дж. Алгебра Компьютер. 17 (2007), 963–997.

[8] Дж. Д. Хамкинс и А. Мясников, Проблема остановки разрешима на множестве асимптотической вероятности один , Notre Dame J. Formal Logic 47 (2006), 515–524.

[9] А. Мясников и А. Рыбалов, Общая сложность неразрешимых задач , Журнал символической логики 73 (2008), 656–673.

[10] А. Рыбалов, О сильно генерической неразрешимости проблемы остановки , Теор. Вычислить. наук. 377 (2007), 268–270.

[11] М. Дж. Фишер и М. О. Рабин, Суперэкспоненциальная сложность арифметики Пресбургера , Труды симпозиума SIAM-AMS по прикладной математике 7 (1974) 2741.

[12] А. Рыбалов, Общая сложность арифметики Пресбургера , 356–361, Второй международный симпозиум по информатике в России, CSR 2007, Конспекты лекций по информатике 4649, Springer 2007.

[13] Р. Гилман, А. Г. Мясников, А. Д. Мясников и А. Ушаков, Отчет о дженериках.Сложность случая, Вестник Омского университета, Спецвыпуск, 2007, 103–110.

[14] А.Д. Мясников, Общая сложность и односторонние функции , Группы, сложность и криптография, 1, (2009), 13–31.

[15] Р. Гилман, А. Г. Мясников, А. Д. Мясников, А. Ушаков, Новые разработки в области обмена ключами коммутаторов , Учеб. Первый межд. Конф. по символическим вычислениям и криптографии (SCC-2008), Пекин, 2008 г.

[16] А. Г. Мясников, В. Шпильрайн, А. Ушаков, Практическая атака на криптографический протокол на основе группы кос , в конспектах лекций по информатике, 3621, Springer Verlag,2005, 86–96.

[17] А.Д. Мясников и А. Ушаков, Группы атак и кос на основе длины: криптоанализ протокола обмена ключами Аншеля-Аншеля-Гольдфельда , в Криптография с открытым ключом PKC 2007, 76–88, Конспекты лекций по вычислениям. Sci., 4450, Шпрингер, Берлин, 2007.

[18] А. Г. Мясников и А. Ушаков, Случайные подгруппы и анализ атак на основе длины и факторизации , Журнал математической криптологии, 2 (2008), 29–61.

[19] А. Мясников и А. Рыбалов, Общая сложность неразрешимых задач , Журнал символической логики 73 (2008), 656–673.

[20] А. Р. Мейер и М. С. Патерсон, С какой частотой кажутся трудными неразрешимые проблемы? , Технический отчет MIT, MIT/LCS/TM-126, февраль 1979 г.

[21] Ю. Гуревич, Игра «Челленджер-решатель»: вариации на тему P =?NP , Колонка «Логика в информатике», Бюллетень EATCS, октябрь 1989 г., стр. 112-121.

[22] Р. Импальяццо, Личный взгляд на сложность в среднем случае , в материалах 10-й ежегодной конференции по теории структуры сложности - SCT 1995, Компьютерное общество IEEE, 1995, стр. 134.

[23] Ю. Гуревич, Средняя полнота случая , Журнал компьютерных и системных наук, 42(1991), 346–398.

[24] А. Богданов, Л. Тревизан, Средняя сложность , Найдено. Теория тенденций. Вычислить. наук. 2 , № 1, 111 с. (2006).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]