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