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

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

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

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

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

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

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

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

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

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

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

FPT

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

Примером может служить проблема выполнимости , параметризованная количеством переменных. Заданная формула размера m с k переменными может быть проверена грубой силой по времени . Вершина крышку размера к в графе порядка п можно найти во время , так что эта проблема также находится в FPT. ${\ Displaystyle О (2 ^ {к} м)}$${\ Displaystyle О (2 ^ {к} п)}$

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

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

FPT закрывается параметризованным сокращением, называемым сокращением fpt , которое одновременно сохраняет размер экземпляра и параметр.

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

W иерархия

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

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

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

W [1]

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

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

W [2]

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

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

Вт [ т ]

${\ displaystyle W [t]}$может быть определен с использованием семейства задач SAT с взвешенным весом- t- глубиной- 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. Здесь Weighted t -Normalize SAT представляет собой следующую проблему: ${\ displaystyle t \ geq 2}$${\ displaystyle W [t]}$

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

W [ P ]

W [ P ] - это класс проблем, которые могут быть решены машиной Тьюринга с недетерминированным временем, которая делает самое большее недетерминированный выбор в вычислениях ( машина Тьюринга с ограничением k ). Flum & Grohe (2006)${\ Displaystyle ч (к) \ cdot {| х |} ^ {O (1)}}$${\ Displaystyle О (е (К) \ CDOT \ журнал п)}$${\ Displaystyle (х, к)}$

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

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

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

XP

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

пара-НП

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

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

Иерархия

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

Заметки

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

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

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

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