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

В информатике, параметризованная сложность представляет собой ветвь теории сложности вычислений, которая фокусируется на классификацию вычислительных задач в соответствии с присущими им трудностью в отношении нескольких параметров ввода или вывода. Затем сложность проблемы измеряется как функция этих параметров. Это позволяет классифицировать 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})}$

• 1 Классы сложности
  • 1.1 FPT
  • 1.2 W иерархия
    • 1,2,1 Вт [1]
    • 1.2.2 Вт [2]
    • 1.2.3 Вт [ т ]
    • 1.2.4 Вт [ P ]
  • 1,3 опыта
  • 1.4 пара-НП
  • 1.5 Иерархия
• 2 Примечания
• 3 ссылки
• 4 Внешние ссылки

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 amp; 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].

1. ^ Чен, Кандж и Ся 2006
2. ^ Grohe (1999)
3. Перейти ↑ Buss, Jonathan F, Islam, Tarique (2006). «Упрощение иерархии утка». Теоретическая информатика. 351 (3): 303–313. DOI : 10.1016 / j.tcs.2005.10.002. CS1 maint: несколько имен: список авторов ( ссылка )
4. ^ Flum amp; Grohe, стр. 39.Ошибка sfnp: нет цели: CITEREFFlumGrohe ( справка )

• Чен, Цзианэр; 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 по параметризованной сложности
• Сборник параметризованных задач