Сложность общего случая - это подполе теории вычислительной сложности, которая изучает сложность вычислительных задач на «большинстве входов».
Общая сложность - это способ измерения сложности вычислительной проблемы путем игнорирования небольшого набора нерепрезентативных входных данных и рассмотрения наихудшей сложности для остальных. Малый определяется в терминах асимптотической плотности. Очевидная эффективность общей сложности случая заключается в том, что для широкого круга конкретных вычислительных задач наиболее сложные случаи кажутся редкими. Типичные примеры относительно просты.
Этот подход к сложности возник в комбинаторной теории групп , вычислительная традиция которой восходит к началу прошлого века. Понятие общей сложности было введено в работе 2003 года [1] , где авторы показали , что для широкого класса конечно порожденных групп родовой временной сложности некоторых классических задач решения из комбинаторной теории групп, а именно проблем тождества , сопряженность и членства проблема , линейны.
Подробное описание общей сложности кейсов можно найти в опросах. [2] [3]
Основные определения
Асимптотическая плотность
Пусть I - бесконечный набор входных данных для вычислительной задачи.
Определение 1. Функция размера на I - это картас бесконечным диапазоном. Шар радиуса n равен.
Если входные данные закодированы как строки в конечном алфавите, размер может быть длиной строки.
Позволять - ансамбль вероятностных распределений, гдеэто распределение вероятностей на. Если шары конечны, то каждое можно принять за равновероятное распределение, что является наиболее частым случаем. Обратите внимание, что только конечное числоможет быть пустым или иметь ; мы их игнорируем.
Определение 2. Асимптотическая плотность подмножества является когда этот предел существует.
Когда шары конечны и - равновероятная мера,
В этом случае часто удобно использовать шары. вместо шаров и определить . Рассуждение с использованием теоремы Штольца показывает, что существует, если делает, и в этом случае они равны.
Определение 3. является общим, если и незначительно, если . X является экспоненциально (суперполиномиально) общим, если сходимость к пределу в определении 2 является экспоненциально (суперполиномиально) быстрой и т. Д.
Общее подмножество X асимптотически велико. Будет ли X выглядеть большим на практике, зависит от того, насколько быстро сходится к 1. Суперполиномиальная сходимость кажется достаточно быстрой.
Классы общей сложности
Определение 4 алгоритма в GenP (обобщенно полиномиальное время) , если он никогда не дает неправильные ответы , и если он дает правильные ответы в полиномиальное время на родовой наборе входов. Проблема в GenP, если он допускает алгоритм в GenP . Аналогично для GenL (в общем линейное время ), GenE (в общем экспоненциальное время с линейной экспонентой) GenExp (в общем экспоненциальное время) и т. Д. ExpGenP является подклассом GenP, для которого соответствующий общий набор является экспоненциально универсальным.
В целом для любого мы можем определить класс Gen (f), соответствующий временной сложности O ( 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 является подмножеством множества частично вычислимых функций из к , то, если F или его дополнение не пусто, проблема определения того, вычисляет ли конкретная машина Тьюринга функцию из F, является неразрешимой. Следующая теорема дает общий вариант.
Теорема 1 [19] Пусть I - множество всех машин Тьюринга. Если F является подмножеством множества всех частично вычислимых функций издля себя такое , что F и его дополнение оба не пусто, то проблема принятия решения вычисляет ли или нет данная машина Тьюринга функции из F не разрешима на любой экспоненциально общего подмножества I .
- Следующие теоремы взяты из: [1]
Теорема 2 Множество формальных языков, которые вычислимы в общем случае, имеют нулевую меру.
Теорема 3 Существует бесконечная иерархия общих классов сложности. Точнее, для правильной функции сложности f ,.
- Следующая теорема показывает, что точно так же, как в распределительных NP-задачах существуют полные задачи среднего случая ,
есть также общие проблемы с полными случаями. Аргументы в общем случае аналогичны аргументам в среднем случае, а полная задача для общего случая также является полной в среднем случае. Это распределенная ограниченная проблема остановки .
Теорема 4 [2] Существует понятие обобщенного полиномиального сокращения, относительно которого проблема остановки с ограниченным распределением является полной в классе распределительных задач NP.
Сравнение с предыдущей работой
Почти полиномиальное время
Мейер и Патерсон [20] определяют алгоритм как почти полиномиальное время, или APT, если он останавливается в течение p (n) шагов на всех, кроме p (n) входов размера n . Понятно, что алгоритмы APT входят в наш класс GenP . Мы видели несколько полных проблем NP в GenP , но Мейер и Патерсон показывают, что это не относится к APT. Они доказывают, что NP полная проблема сводится к проблеме в APT тогда и только тогда, когда P = NP . Таким образом, APT кажется гораздо более ограничительным, чем GenP .
Средняя сложность
Общая сложность случая аналогична сложности среднего случая . Однако есть некоторые существенные отличия. Общая сложность случая - это прямая мера производительности алгоритма на большинстве входных данных, в то время как средняя сложность случая дает меру баланса между легкими и сложными случаями. Вдобавок к неразрешимым проблемам естественным образом относится сложность общего случая .
Предполагать алгоритм, временная сложность которого , полиномиален на в среднем. Что мы можем сделать о поведении на типовых входах?
Пример 1 Пусть I будет набором всех слов над и определите размер быть длиной слова, . Определятьнабор слов длины n , и предположим, что каждое- равновероятная мера. Предположим, что T (w) = n для всех слов, кроме одного, в каждом, а также на исключительные слова.
В этом примере T определенно полиномиален на типичных входах, но T в среднем не полиномиален. T находится в GenP .
Пример 2 Сохраните I и как и раньше, но определите а также . В среднем T является полиномиальным, хотя на типичных входных данных оно экспоненциально. T не входит в GenP .
В этих двух примерах общая сложность более тесно связана с поведением типичных входных данных, чем средняя сложность случая. Средняя сложность кейсов измеряет кое-что еще: баланс между частотой сложных случаев и степенью сложности. [21] [22] Грубо говоря, алгоритм, который в среднем является полиномиальным временем, может иметь только субполиномиальную часть входных данных, для вычисления которых требуется суперполиномиальное время.
Тем не менее, в некоторых случаях общая и средняя сложность довольно близки друг к другу. Функция полиномиален на -среднее по сферам, если есть такой, что где ансамбль, индуцированный . Если f полиномиален на-среднее на сферах, f полиномиальна на-среднее, и для многих распределений верно обратное [23]
Теорема 5 [2] Если функция полиномиален на -среднее по сферам, то f в общем случае полиномиален относительно сферической асимптотической плотности.
Теорема 6 [2] Предположим, что полный алгоритмимеет субэкспоненциальную временную границу T и частичный алгоритмдля той же проблемы есть в ExpGenP по отношению к ансамблю соответствующий вероятностной мере на входах I для. Тогда есть полный алгоритм, который-средняя временная сложность.
Безошибочные эвристические алгоритмы
В статье 2006 года Богданов и Тревизан вплотную подошли к определению общей сложности случая. [24] Вместо частичных алгоритмов они рассматривают так называемые безошибочные эвристические алгоритмы. Это полные алгоритмы, которые могут дать сбой при остановке с выводом «?». Класс AvgnegP определяется как состоящий из всех безошибочных эвристических алгоритмов A, которые выполняются за полиномиальное время и для которых вероятность отказа нанезначительно, то есть суперполиномиально быстро сходится к 0. AvgnegP является подмножеством GenP . Безошибочные эвристические алгоритмы по сути такие же, как алгоритмы с доброкачественными ошибками, определенные Impagliazzo, где алгоритмы с полиномиальным временем в среднем характеризуются в терминах так называемых схем доброкачественных алгоритмов.
Рекомендации
- ^ a b c И. Капович, А. Мясников, П. Шупп и В. Шпильрайн, Общая сложность случая, проблемы принятия решений в теории групп и случайные блуждания , J. Algebra, vol. 264 (2003), 665–694.
- ^ a b c d e f Р. Гилман, А. Г. Мясников, А. Д. Мясников, А. Ушаков, Общая сложность случая , неопубликованный первый черновик книги, 143 страницы.
- ^ Р. Гильман, А.Г. Мясников, А.Д. Мясников, А. Ушаков, Отчет об общей сложности случая , Вестник Омского университета, Специальный выпуск, 2007, 103–110.
- ↑ А. Ушаков, Диссертация , Городской университет Нью-Йорка, 2005.
- ^ Р. Гилман, Трудные проблемы теории групп , доклад, сделанный на Международной конференции по геометрическим и комбинаторным методам в теории групп и теории полугрупп, 18 мая 2009 г.
- ^ И. Капович, П. Шупп, В. Шпильрайн, Общие свойства алгоритма Уайтхеда и жесткость изоморфизма случайных групп с одним соотношением , Pacific J. Math. 223 (2006)
- ^ А. В. Боровик, А. Г. Мясников, В. Н. Ремесленников, Общая сложность проблемы сопряженности в HNN-расширениях и алгоритмической стратификации групп Миллера , Междунар. J. Algebra Comput. 17 (2007), 963–997.
- ^ JD Хэмкинс и А. Мясников, Проблема остановки разрешима на множестве асимптотической вероятности один , Нотр-Дам Дж. Формальная логика 47 (2006), 515–524.
- ^ А. Мясников и А. Рыбалов, Общая сложность неразрешимых проблем , Журнал символической логики 73 (2008), 656–673.
- ^ А. Рыбалов, О сильно общей неразрешимости проблемы остановки , Теорет. Comput. Sci. 377 (2007), 268–270.
- ^ MJ Фишер и М.О. Рабин, Суперэкспоненциальная сложность пресбургеровской арифметики , Труды симпозиума SIAM-AMS по прикладной математике 7 (1974) 2741.
- ^ А. Рыбалов, Generic сложность Пресбургера арифметики , 356-361 во Втором Международном симпозиуме по информатике в России CSR 2007, Lecture Notes вкомпьютерных наук 4649, Springer 2007.
- ^ Р. Гильман, А.Г. Мясников, А.Д. Мясников, А. Ушаков, Отчет об общей сложности случая, Вестник Омского университета, Специальный выпуск, 2007, 103–110.
- ^ А.Д. Мясников, Общая сложность и односторонние функции , группы, сложность и криптография, 1, (2009), 13–31.
- ^ Р. Гильман, А. Г. Мясников, А. Д. Мясников, А. Ушаков, Новые разработки в коммутаторном обмене ключами , Proc. Первый Int. Конф. по символическим вычислениям и криптографии (SCC-2008), Пекин, 2008.
- ^ А.Г. Мясников, В. Шпильрайн, А. Ушаков, Практическая атака на криптографический протокол на основе группы кос , в Lecture Notes in Computer Science, 3621, Springer Verlag, 2005, 86–96.
- ^ А.Д. Мясников и А. Ушаков, Атака на основе длины и группы кос: криптоанализ протокола обмена ключами Аншеля – Аншеля – Голдфельда , в Криптографии с открытым ключом PKC 2007, 76–88, Lecture Notes in Comput. Sci., 4450, Springer, Берлин, 2007.
- ^ А.Г. Мясников, А. Ушаков, Случайные подгруппы и анализ атак на основе длины и фактора , Журнал математической криптологии, 2 (2008), 29–61.
- ^ А. Мясников и А. Рыбалов, Общая сложность неразрешимых проблем , Журнал символической логики 73 (2008), 656–673.
- ^ А. Р. Мейер и М. С. Патерсон, С какой периодичностью трудноразрешимые проблемы кажутся сложными? , Технический отчет MIT, MIT / LCS / TM-126, февраль 1979 г.
- ↑ Y. Gurevich, The Challenger-solver game: вариации на тему P =? NP , Logic in Computer Science Column, The Bulletin of the EATCS, October 1989, p.112-121.
- ^ Р. Импальяццо, Личный взгляд на сложность в среднем случае , в Протоколах 10-й ежегодной конференции по теории сложности - SCT 1995, IEEE Computer Society, 1995, стр. 134.
- ^ Ю. Гуревич, Полнота среднего случая , Журнал компьютерных и системных наук, 42 (1991), 346–398.
- ^ А. Богданов, Л. Тревизан, Сложность среднего случая , Найдено. Trends Theor. Comput. Sci. 2 , №1, 111 с. (2006) ..