Введение

В компьютерной науке параметризованная сложность — это раздел теории вычислительной сложности, который фокусируется на классификации вычислительных задач в соответствии с их внутренней сложностью относительно нескольких параметров входных или выходных данных. Сложность задачи затем измеряется как функция этих параметров. Это позволяет классифицировать NP-трудные задачи с большей детализацией, чем в классическом подходе, где сложность задачи измеряется только как функция от количества битов во входных данных. Впервые это было продемонстрировано, по-видимому, в. Первая систематическая работа по параметризованной сложности была выполнена. При предположении, что P ≠ NP, существует множество естественных задач, требующих суперполиномиального времени выполнения, если сложность измеряется только с точки зрения размера входных данных, но которые могут быть вычислены за время, полиномиальное относительно размера входных данных и экспоненциальное или хуже относительно параметра k. Следовательно, если k фиксировано на небольшом значении, а рост функции относительно k относительно мал, то такие задачи все еще можно считать «разрешимыми», несмотря на их традиционную классификацию как «неразрешимых». Существование эффективных, точных и детерминированных алгоритмов решения NP-полных или NP-трудных задач считается маловероятным, если входные параметры не фиксированы; все известные алгоритмы решения этих задач требуют времени, экспоненциального (а значит, в частности, суперполиномиального) относительно общего размера входных данных. Однако некоторые задачи могут быть решены алгоритмами, которые экспоненциальны только относительно размера фиксированного параметра, но полиномиальны относительно размера входных данных. Такой алгоритм называется алгоритмом с фиксированным параметром (FPT), поскольку задача может быть решена эффективно (т.е. за полиномиальное время) при постоянных значениях фиксированного параметра. Задачи, в которых какой-то параметр k фиксирован, называются параметризованными задачами. Параметризованная задача, для которой существует такой алгоритм FPT, называется задачей с фиксированным параметром и принадлежит классу , а раннее название теории параметризованной сложности — фиксированная параметрическая разрешимость. Многие задачи имеют следующую форму: даны объект x и неотрицательное целое число k, обладает ли x свойством, зависящим от k? Например, для задачи о вершинном покрытии параметром может быть количество вершин в покрытии. Во многих приложениях, например при моделировании коррекции ошибок, можно предположить, что параметр «маленький» по сравнению с общим размером входных данных. Тогда сложно найти алгоритм, экспоненциальный только относительно k, а не относительно размера входных данных. Таким образом, параметризованную сложность можно рассматривать как двухмерную теорию сложности. Эта концепция формализуется следующим образом: параметризованная задача — это язык , где является конечным алфавитом. Второй компонент называется параметром задачи. Параметризованная задача L является задачей с фиксированным параметром, если вопрос "?" может быть решен за время выполнения , где f — произвольная функция, зависящая только от k. Соответствующий класс сложности называется FPT. Например, существует алгоритм, решающий задачу о вершинном покрытии за время , где n — количество вершин, а k — размер вершинного покрытия. Это означает, что вершинное покрытие является задачей с фиксированным параметром, с размером решения в качестве параметра.

ФПТ

FPT содержит задачи, разрешимые за фиксированное время, которые могут быть решены за время для некоторой вычислимой функции f. Обычно эта функция представляется в виде экспоненты, такой как , но определение допускает функции, растущие еще быстрее. Это имеет важное значение для ранней истории этого класса задач. Ключевым аспектом определения является исключение функций вида , например, .

Класс FPL (фиксированный параметр линейный) – это класс задач, разрешимых за время для некоторой вычислимой функции f. Таким образом, FPL является подклассом FPT. Примером является задача булевой выполнимости, параметризованная числом переменных. Учитывая формулу размера m с k переменными, ее можно проверить полным перебором за время . Вершинное покрытие размера k в графе порядка n можно найти за время , следовательно, задача вершинного покрытия также принадлежит FPL. Примером задачи, которая, как считается, не входит в FPT, является раскраска графа, параметризованная числом цветов. Известно, что 3-раскраска является NP-трудной задачей, и алгоритм раскраски графа в k цветов за время для работал бы за полиномиальное время относительно размера входных данных. Следовательно, если бы раскраска графа, параметризованная числом цветов, принадлежала FPT, то P = NP. Существует несколько альтернативных определений FPT. Например, требование к времени выполнения можно заменить на . Кроме того, параметризованная задача находится в FPT, если у нее есть так называемое ядро. Кернелизация – это метод предварительной обработки, который сводит исходный экземпляр к его "жесткому ядру" – возможно, значительно меньшему экземпляру, эквивалентному исходному, но размер которого ограничен функцией параметра. FPT замкнут относительно параметризованного понятия редукций, называемых fpt-редукциями. Такие редукции преобразуют экземпляр некоторой задачи в эквивалентный экземпляр другой задачи (с ) и могут быть вычислены за время , где является полиномом. Очевидно, что FPT содержит все задачи, разрешимые за полиномиальное время. Более того, он содержит все задачи оптимизации в NP, для которых существует эффективная полиномиальная схема аппроксимации времени (EPTAS).

Иерархия W

Иерархия W представляет собой набор классов вычислительной сложности. Параметризованная задача принадлежит классу W[i], если каждый экземпляр может быть преобразован (за fpt время) в комбинаторную схему, имеющую ширину не более i, таким образом, что задача разрешима тогда и только тогда, когда существует такое присваивание значений входам, при котором ровно k входам присвоено значение 1. Ширина – это максимальное количество логических элементов с веером входа больше двух на любом пути от входа к выходу. Общее количество логических элементов на путях (известное как глубина) должно быть ограничено константой, справедливой для всех экземпляров задачи. Отметим, что и для всех классов в иерархии W также замкнуты относительно fpt-сокращения. Полной задачей для W[i] является взвешенная i-нормализованная выполнимость: задана булева формула, представленная как конъюнкция дизъюнкций конъюнкций из возможно инвертированных переменных, с слоями конъюнкций или дизъюнкций (и i чередованиями между конъюнкцией и дизъюнкцией), можно ли ее выполнить, установив ровно k переменным значение 1? Многие естественные вычислительные задачи находятся на нижних уровнях, W[1] и W[2].

W[P]

W[P] — это класс задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, совершающей не более *n* недетерминированных выборов в процессе вычисления (на *k*-ограниченной машине Тьюринга). Известно, что FPT содержится в W[P], и предполагается, что это включение стро́гое. Однако разрешение этого вопроса подразумевало бы решение проблемы P против NP. Другая связь с непараметризованной вычислительной сложностью заключается в том, что FPT равно W[P] тогда и только тогда, когда задача выполнимости булевой формулы может быть решена за время , или тогда и только тогда, когда существует вычислимая, неубывающая, неограниченная функция *f* такая, что все языки, распознаваемые недетерминированной машиной Тьюринга за полиномиальное время, использующей *f(n)log n* недетерминированных выборов, находятся в P.

W[P] можно условно рассматривать как класс задач, в которых дано множество *S* из *n* элементов, и требуется найти подмножество размера *k*, удовлетворяющее определённому свойству. Мы можем закодировать каждый выбор как список из *k* целых чисел, представленных в двоичном виде. Поскольку наибольшее из этих чисел может быть равно *n*, для каждого числа требуется бит. Следовательно, для кодирования одного выбора требуется всего битов. Таким образом, мы можем выбрать подмножество, используя недетерминированных выборов.

XP

XP — это класс параметризованных задач, которые могут быть решены за время f(k) для некоторой вычислимой функции f. Эти задачи называются кусочно-полиномиальными, поскольку для каждого фиксированного k существует полиномиальный алгоритм, хотя показатель степени полинома может различаться для разных k. Это следует отличать от FPT, где допускается лишь различный постоянный множитель для каждого значения k. XP содержит FPT, и известно, что это включение является строгим, что было доказано методом диагонализации.

пара-НП

para NP — это класс параметризованных задач, которые могут быть решены недетерминированным алгоритмом за время для некоторой вычислимой функции f. Известно, что если и только если проблема является para NP-трудной, если она уже трудна для постоянного значения параметра. То есть, существует "срез" с фиксированным k, который является трудным. Параметризованная задача, которая является трудной, не может принадлежать классу , если классическим примером трудной параметризованной задачи является раскраска графа, параметризованная числом k цветов, которая уже трудна для (см. Раскраска графа#Вычислительная сложность).

Иерархия

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