Параметризованная сложность

В информатике , параметризованная сложность — это раздел теории сложности вычислений который фокусируется на классификации вычислительных задач в соответствии с присущей им сложностью в отношении нескольких параметров ввода или вывода. Затем сложность проблемы измеряется как функция этих параметров. Это позволяет классифицировать NP-сложные проблемы в более точном масштабе, чем в классической постановке, где сложность проблемы измеряется только как функция количества бит во входных данных. По-видимому, это было впервые продемонстрировано Гуревичем, Стокмейером и Вишкиным (1984) . Первая систематическая работа по параметризованной сложности была проведена Дауни и Феллоуз (1999) .

В предположении, что P ≠ NP , существует множество естественных задач, которые требуют суперполиномиального времени выполнения , когда сложность измеряется только с точки зрения размера входных данных, но которые вычислимы за время, которое является полиномиальным по размеру входных данных и экспоненциальным или хуже по параметру. к . Следовательно, если k фиксировано на небольшом значении и рост функции по k относительно невелик, то такие проблемы все равно можно считать «разрешимыми», несмотря на их традиционную классификацию как «трудноразрешимые».

Существование эффективных, точных и детерминированных алгоритмов решения NP-полных или, иначе, NP-трудных задач считается маловероятным, если входные параметры не фиксированы; все известные алгоритмы решения этих задач требуют времени, которое экспоненциально (в частности, суперполиномиально) зависит от общего размера входных данных. Однако некоторые проблемы можно решить с помощью алгоритмов, которые являются экспоненциальными только по размеру фиксированного параметра и полиномиальными по размеру входных данных. Такой алгоритм называется управляемым алгоритмом с фиксированным параметром (FPT), поскольку задача может быть решена эффективно (т. е. за полиномиальное время) для постоянных значений фиксированного параметра.

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

Многие задачи имеют следующий вид: если задан объект x и целое неотрицательное число k , то есть ли у x какое-то свойство, зависящее от k ? Например, для задачи вершинного покрытия параметром может быть количество вершин в покрытии. Во многих приложениях, например, при моделировании коррекции ошибок, можно предположить, что параметр «маленький» по сравнению с общим размером входных данных. Тогда сложно найти алгоритм, который был бы экспоненциальным только по k , а не по размеру входных данных.

Таким образом, параметризованную сложность можно рассматривать как двумерную теорию сложности. Это понятие формализуется следующим образом:

Параметризованная задача – это язык $L\subseteq \Sigma ^{*}\times \mathbb {N}$, где $\Sigma$ является конечным алфавитом. Второй компонент называется параметром задачи.

Параметризованная задача L разрешима с фиксированным параметром, если вопрос « $(x,k)\in L$?" можно решить во время выполнения $f(k)\cdot |x|^{O(1)}$, где f — произвольная функция, зависящая только от k . Соответствующий класс сложности называется FPT .

Например, существует алгоритм, решающий задачу вершинного покрытия в $O(kn+1.274^{k})$ время, где n — количество вершин, а k — размер вершинного покрытия. Это означает, что вершинное покрытие является управляемым с фиксированным параметром, используя размер решения в качестве параметра.

Классы сложности

ФПТ

FPT содержит решаемые задачи с фиксированными параметрами , то есть те, которые можно решить вовремя. $f(k)\cdot {|x|}^{O(1)}$ для некоторой вычислимой функции f . Обычно эту функцию рассматривают как одну экспоненту, например $2^{O(k)}$, но определение допускает функции, которые растут еще быстрее. Это важно для большей части ранней истории этого класса. Важнейшей частью определения является исключение функций вида $f(n,k)$, такой как $k^{n}$.

Класс FPL (линейный с фиксированным параметром) — это класс задач, решаемых за время. $f(k)\cdot |x|$ для некоторой вычислимой функции f . Таким образом, FPL является подклассом FPT. Примером является булева проблема выполнимости , параметризованная количеством переменных. Заданную формулу размера m с k переменными можно проверить перебором за время. $O(2^{k}m)$. Вершинное покрытие размера k в графе порядка n можно найти за время $O(2^{k}n)$, поэтому проблема покрытия вершин также существует в FPL.

Примером проблемы, которой, как считается, нет в FPT, является раскраска графа , параметризованная количеством цветов. Известно, что 3-раскраска NP-трудна , а алгоритм k- раскраски графа за время $f(k)n^{O(1)}$ для $k=3$ будет работать за полиномиальное время в зависимости от размера входных данных. Таким образом, если раскраска графа, параметризованная количеством цветов в FPT, то P = NP .

Существует ряд альтернативных определений FPT. Например, требование времени выполнения можно заменить на $f(k)+|x|^{O(1)}$. Также параметризованная проблема есть в FPT, если у него есть так называемое ядро. Кернелизация — это метод предварительной обработки, который сводит исходный экземпляр к его «жесткому ядру», возможно, гораздо меньшему экземпляру, который эквивалентен исходному экземпляру, но имеет размер, ограниченный функцией в параметре.

FPT замкнут в соответствии с параметризованным понятием сокращений, называемым fpt-reductions . Такие сокращения преобразуют экземпляр $(x,k)$ какой-то проблемы в эквивалентный экземпляр $(x',k')$ другой проблемы (с $k'\leq g(k)$) и может быть вычислено за время $f(k)\cdot p(|x|)$ где $p$ является полиномом.

Очевидно, что FPT содержит все задачи, вычислимые за полиномиальное время. Более того, он содержит все задачи оптимизации в NP, которые позволяют использовать эффективную схему аппроксимации с полиномиальным временем (EPTAS) .

W иерархия

Иерархия W представляет собой набор классов вычислительной сложности. Параметризованная задача находится в классе W [ i ], если каждый экземпляр $(x,k)$ может быть преобразовано (за fpt-время) в комбинаторную схему с утком не более i , такую, что $(x,k)\in L$ тогда и только тогда, когда существует удовлетворяющее присвоение входам, которое присваивает 1 ровно k входам. Уток — это наибольшее количество логических единиц с разветвлением более двух на любом пути от входа к выходу. Общее количество логических единиц на путях (известное как глубина) должно быть ограничено константой, которая справедлива для всех случаев проблемы.

Обратите внимание, что ${\mathsf {FPT}}=W[0]$ и $W[i]\subseteq W[j]$ для всех $i\leq j$. Классы в иерархии W также замкнуты относительно fpt-редукции.

Полная проблема для W [ i ] — это взвешенная i -нормализованная выполнимость : дана булева формула, записанная как И из ИЛИ из И из... возможно отрицательных переменных, с $i+1$ слоев И или ИЛИ (и i чередований между И и ИЛИ), можно ли этого добиться, присвоив ровно k переменным значение 1?

Многие естественные вычислительные задачи занимают нижние уровни W [1] и W [2].

В [1]

Примеры W [1]-полных задач включают в себя

• определение, содержит ли данный граф клику размера k
• определение того, содержит ли данный граф независимый набор размера k
• принятие решения о том, принимает ли данная недетерминированная одноленточная машина Тьюринга в течение k шагов (проблема «короткой машины Тьюринга»). Это также применимо к недетерминированным машинам Тьюринга с f ( k ) лентами и даже f ( k ) из f ( k )-мерных лент, но даже с этим расширением ограничение на размер алфавита ленты f ( k ) является управляемым с фиксированным параметром. Важно отметить, что ветвление машины Тьюринга на каждом шаге может зависеть от n , размера входных данных. Таким образом, машина Тьюринга может исследовать n ^{Хорошо ​ )} вычислительные пути.

В [2]

Примеры W [2]-полных задач включают в себя

• определение того, содержит ли данный граф доминирующий набор размера k
• ли данная недетерминированная многоленточная машина Тьюринга принятие решения о том, принимает в пределах k шагов (проблема принятия короткой многоленточной машины Тьюринга). Важно отметить, что ветвление может зависеть от n (как вариант W[1]), как и от количества лент. Альтернативная W [2]-полная формулировка допускает использование только одноленточных машин Тьюринга, но размер алфавита может зависеть от n .

Вт [ т ]

$W[t]$ можно определить с помощью семейства задач SAT Weighted Weft -t -Depth- d для $d\geq t$: $W[t,d]$ - это класс параметризованных задач, которые fpt-сводятся к этой задаче, и $W[t]=\bigcup _{d\geq t}W[t,d]$.

Здесь Weighted Weft -t -Depth- d SAT представляет собой следующую проблему:

• Входные данные: булева формула с глубиной не более d и утком не более t и числом k . Глубина — это максимальное количество элементов на любом пути от корня к листу, а уток — максимальное количество элементов веера не менее трех на любом пути от корня к листу.
• Вопрос: Имеет ли формула удовлетворительное присвоение веса Хэмминга ровно k ?

Можно показать, что для $t\geq 2$ проблема Weighted t -Normalize SAT завершена для $W[t]$ при fpt-сокращении. Здесь Weighted t -Normalize SAT представляет собой следующую проблему:

• Входные данные: булева формула глубины не более t с логическим элементом И сверху и числом k .
• Вопрос: Имеет ли формула удовлетворительное присвоение веса Хэмминга ровно k ?

В [ П ]

W [ P ] — это класс проблем, которые могут быть решены недетерминированным методом. $h(k)\cdot {|x|}^{O(1)}$-время машины Тьюринга, которая производит не более $O(f(k)\cdot \log n)$ недетерминированный выбор при вычислении $(x,k)$ ( k -ограниченная машина Тьюринга). Флум и Гроэ (2006)

Известно, что FPT содержится в W[P], и включение считается строгим. Однако решение этой проблемы означало бы решение проблемы P и NP .

Другие связи с непараметризованной вычислительной сложностью заключаются в том, что FPT равен W [ P ] тогда и только тогда, когда выполнимость схемы может быть определена вовремя. $\exp(o(n))m^{O(1)}$, или тогда и только тогда, когда существует вычислимая, неубывающая, неограниченная функция f такая, что все языки распознаются недетерминированной машиной Тьюринга с полиномиальным временем, используя ⁠ $f(n)\log n$⁠ недетерминированный выбор находится в P .

W [ P ] можно условно рассматривать как класс задач, в которых у нас есть набор S из n элементов, и мы хотим найти подмножество $T\subset S$ размера k такой, что выполняется определенное свойство. Мы можем закодировать выбор как список из k целых чисел, хранящихся в двоичном формате. Поскольку наибольшее из этих чисел может быть n , $\lceil \log _{2}n\rceil$ биты необходимы для каждого числа. Поэтому $k\cdot \lceil \log _{2}n\rceil$ общее количество битов необходимо для кодирования выбора. Поэтому мы можем выбрать подмножество $T\subset S$ с $O(k\cdot \log n)$ недетерминированный выбор.

XP

XP — это класс параметризованных задач, которые можно решить за время. $n^{f(k)}$ для некоторой вычислимой функции f . Эти задачи называются срезно- полиномиальными в том смысле, что каждый «срез» фиксированного k имеет полиномиальный алгоритм, хотя, возможно, с разным показателем степени для каждого k. Сравните это с FPT, который просто допускает разные постоянные префакторы для каждого значения k. XP содержит FPT, и известно, что это сдерживание строгое за счет диагонализации.

пара-НП

пара-NP — это класс параметризованных задач, которые можно решить недетерминированным алгоритмом за время. $f(k)\cdot |x|^{O(1)}$ для некоторой вычислимой функции f . Известно, что ${\textsf {FPT}}={\textsf {para-NP}}$ тогда и только тогда, когда ${\textsf {P}}={\textsf {NP}}$.

Задача является пара-NP-трудной, если она ${\textsf {NP}}$-hard уже для постоянного значения параметра. То есть существует «кусок» фиксированного k , который ${\textsf {NP}}$-жесткий. Параметризованная задача, которая ${\textsf {para-NP}}$-hard не может принадлежать классу ${\textsf {XP}}$, пока не ${\textsf {P}}={\textsf {NP}}$. Классический пример ${\textsf {para-NP}}$-жесткая параметризованная задача — это раскраска графа , параметризованная числом k цветов, которое уже ${\textsf {NP}}$-трудно для $k=3$ (см. Раскраска графа#Вычислительная сложность ).

Иерархия

Иерархия A представляет собой набор классов вычислительной сложности, аналогичный иерархии W. Однако, хотя иерархия W является иерархией, содержащейся в NP, иерархия A более точно имитирует иерархию полиномиального времени классической сложности. Известно, что выполнено A[1] = W[1].

См. также

• Алгоритм параметризованной аппроксимации . Для задач оптимизации алгоритм, работающий за время FPT, может аппроксимировать решение.

Ссылки

• Чен, Цзянер; Кандж, Ияд А.; Ся, Ге (2006). Улучшены параметризованные верхние границы для вершинного покрытия . Математические основы информатики. Том. 4162. Берлин, Гейдельберг: Springer. стр. 238–249. CiteSeerX   10.1.1.432.831 . дои : 10.1007/11821069_21 . ISBN  978-3-540-37791-7 .
• Сайган, Марк; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015). Параметризованные алгоритмы . Спрингер. стр. 555. ISBN  978-3-319-21274-6 .
• Дауни, Род Г .; Товарищи, Майкл Р. (1999). Параметризованная сложность . Спрингер. ISBN  978-0-387-94883-6 .
• Флум, Йорг ; Гроэ, Мартин (2006). Параметризованная теория сложности . Спрингер. ISBN  978-3-540-29952-3 .
• Фомин Федор Владимирович; Локштанов Даниил; Саураб, Сакет; Зехави, Мейрав (2019). Кернелизация: теория параметризованной предварительной обработки . Издательство Кембриджского университета. п. 528. дои : 10.1017/9781107415157 . ISBN  978-1107057760 . S2CID   263888582 .
• Гуревич Юрий; Стокмейер, Ларри; Вишкин, Узи (1984). Решение NP-сложных задач на графах, близких к деревьям, и приложение к задачам размещения предприятий . Журнал АКМ. п. 459-473.
• Нидермайер, Рольф (2006). Приглашение к алгоритмам с фиксированными параметрами . Издательство Оксфордского университета. ISBN  978-0-19-856607-6 . Архивировано из оригинала 24 сентября 2008 г.
• Гроэ, Мартин (1999). «Описательная и параметризованная сложность». Информатика Логика . Конспекты лекций по информатике. Том. 1683. Шпрингер Берлин Гейдельберг. стр. 14–31. CiteSeerX   10.1.1.25.9250 . дои : 10.1007/3-540-48168-0_3 . ISBN  978-3-540-66536-6 .
• Компьютерный журнал . Том 51, номера 1 и 3 (2008 г.). Компьютерный журнал . Специальный двойной выпуск, посвященный параметризованной сложности, с 15 обзорными статьями, рецензией на книгу и предисловием приглашенных редакторов Р. Дауни, М. Феллоуз и М. Лэнгстона.

Внешние ссылки

• Wiki по параметризованной сложности
• Сборник параметризованных задач