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

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

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

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

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

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

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

А параметризованная задача это язык

{ Displaystyle L substeq Sigma ^ {*} times mathbb {N}}

, куда

{ displaystyle Sigma}

конечный алфавит. Второй компонент называется параметр проблемы.

Параметризованная проблема

L

является управляемый с фиксированными параметрами если вопрос «

{ Displaystyle (х, к) в L}

? » можно решить во время работы

{ Displaystyle е (к) cdot | х | ^ {O (1)}}

, куда

ж

произвольная функция, зависящая только от

k

. Соответствующий класс сложности называется FPT.

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

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

FPT

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

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

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

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

FPT закрывается под параметризованным снижение называется fpt-уменьшение, который одновременно сохраняет размер экземпляра и параметр.

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

W иерархия

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

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

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

W[1]

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

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

W[2]

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

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

W[т]

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

Здесь, Утяжеленный уток $т$ -Глубина- $d$ СИДЕЛ это следующая проблема:

Вход: логическая формула глубины не более $d$ и уток самое большее $т$ , и число $k$ . В глубина - максимальное количество ворот на любом пути от корня до листа, а уток это максимальное количество ворот фан-ин не менее трех на любом пути от корня до листа.
Вопрос: имеет ли формула точное присвоение веса Хэмминга? $k$ ?

Можно показать, что проблема Взвешенная $т$ -Normalize SAT завершен для ${ displaystyle W [t]}$ под fpt-сокращения.^[3]Здесь, Взвешенный $т$ -Normalize SAT это следующая проблема:

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

W[п]

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

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

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

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

XP

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

пара-НП

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

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

Иерархия

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

Примечания

^ Чен, Кандж и Ся 2006
^ Grohe (1999)
^ Басс, Джонатан Ф, Ислам, Tarique (2006). «Упрощение иерархии утка». Теоретическая информатика. 351 (3): 303–313. Дои:10.1016 / j.tcs.2005.10.002.CS1 maint: несколько имен: список авторов (связь)
^ Flum & Grohe, п. 39.

внешняя ссылка

[1] Чен, Кандж и Ся 2006

[2] Grohe (1999)

[3] Басс, Джонатан Ф, Ислам, Tarique (2006). «Упрощение иерархии утка». Теоретическая информатика. 351 (3): 303–313. Дои:10.1016 / j.tcs.2005.10.002.CS1 maint: несколько имен: список авторов (связь)

[FOOTNOTEFlumGrohe39-4] Flum & Grohe, п. 39.

[1]

[2]

[3]

[4]