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

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

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

В предположении, что P ≠ NP , существует множество естественных задач, которые требуют суперполиномиального времени выполнения , когда сложность измеряется только с точки зрения размера входных данных, но которые вычислимы за время, которое является полиномиальным по размеру входных данных и экспоненциальным или хуже по параметру. к . Следовательно, если 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 -раскраски графа за время for будет работать за полиномиальное время от размера входных данных. Таким образом, если раскраска графа, параметризованная количеством цветов в FPT, то P = NP . ${\displaystyle f(k)n^{O(1)}}$ ${\displaystyle k=3}$

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

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

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

W иерархия

Иерархия 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

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

пара-НП

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

Задача является пара-NP-трудной , если она является -трудной уже для постоянного значения параметра. То есть существует «кусок» фиксированного k , который является -жестким. Параметризованная задача, являющаяся -hard, не может принадлежать классу , если только . Классическим примером -трудной параметризованной задачи является раскраска графа , параметризованная числом 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 Journal по вычислительной технике . 24 (4): 873–921. дои : 10.1137/S0097539792228228. ISSN  0097-5397.
4. Басс, Джонатан Ф; Ислам, Тарик (2006). «Упрощение иерархии утка». Теоретическая информатика . 351 (3): 303–313. дои : 10.1016/j.tcs.2005.10.002 .
5. Флум и Гроэ (2006), с. 39.

Рекомендации

• Чен, Цзянер; Кандж, Ияд А.; Ся, Ге (2006). Улучшены параметризованные верхние границы для покрытия вершин . Математические основы информатики. Том. 4162. Берлин, Гейдельберг: Springer. стр. 238–249. CiteSeerX  10.1.1.432.831 . дои : 10.1007/11821069_21. ISBN 978-3-540-37791-7.
• Циган, Марек; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015). Параметризованные алгоритмы . Спрингер. п. 555. ИСБН 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 по параметризованной сложности
• Сборник параметризованных задач