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

Раздел теории сложности вычислений

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

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

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

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

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

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

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

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

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

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

ФПТ

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

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

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

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

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

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

Втиерархия

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

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

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

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

Вт[1]

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

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

Вт[2]

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

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

Вт[т]

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

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

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

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

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

Вт[П]

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

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

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

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

ХР

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

пара-НП

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

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

Иерархия

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

Смотрите также

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

Примечания

1. Чэнь, Кань и Ся 2006
2. Гроэ (1999)
3. Дауни, Род Г.; Феллоуз, Майкл Р. (август 1995 г.). «Распознаваемость и полнота с фиксированными параметрами I: основные результаты». Журнал SIAM по вычислениям . 24 (4): 873–921. doi :10.1137/S0097539792228228. ISSN  0097-5397.
4. Басс, Джонатан Ф.; Ислам, Тарик (2006). «Упрощение иерархии утка». Теоретическая информатика . 351 (3): 303–313. doi : 10.1016/j.tcs.2005.10.002 .
5. Флум и Гроэ (2006), стр. 39.

Ссылки

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

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

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