Введение

Тип вычислительной задачи
В теории вычислительной сложности, функциональная задача — это вычислительная задача, для которой ожидается единственный выход (полной функции) для каждого входа, однако выход более сложен, чем у задачи принятия решения. Для функциональных задач выход не ограничивается ответами "да" или "нет".

Примеры

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

Для заданной булевой формулы с переменными , найдите такое присваивание значений переменным , при котором формула принимает значение "истина", или определите, что такого присваивания не существует. В этом случае отношение задается кортежами, состоящими из соответствующим образом закодированных булевых формул и выполнимых присваиваний. В то время как алгоритм SAT, получив на вход формулу , должен возвращать только "невыполнимо" или "выполнимо", алгоритм FSAT должен возвращать одно из выполнимых присваиваний в последнем случае. Другие известные примеры включают задачу коммивояжера, которая требует найти оптимальный маршрут, и задачу факторизации целых чисел, которая требует найти список множителей.

Отношение к другим классам сложности

Рассмотрим произвольную задачу принятия решений в классе NP. По определению NP, для каждого экземпляра задачи, на который получен ответ "да", существует полиномиального размера сертификат, служащий доказательством этого ответа "да". Таким образом, множество этих пар (экземпляр, сертификат) образует отношение, представляющее функциональную задачу "для данного в , найти сертификат для ". Эта функциональная задача называется функциональным вариантом ; она принадлежит классу FNP. FNP можно рассматривать как функциональный аналог NP, в том смысле, что решения задач FNP могут быть эффективно проверены (то есть за полиномиальное время относительно длины входных данных), но не обязательно эффективно найдены. В отличие от этого, класс FP, который можно рассматривать как функциональный аналог P, состоит из функциональных задач, решения которых могут быть найдены за полиномиальное время.

Саморедуктивность

Заметьте, что задачу FSAT, представленную выше, можно решить, используя лишь полиномиальное число вызовов подпрограммы, решающей задачу SAT: алгоритм может сначала запросить, является ли формула выполнимой. Затем алгоритм может зафиксировать переменную в TRUE и запросить снова. Если полученная формула остаётся выполнимой, алгоритм оставляет переменную зафиксированной в TRUE и продолжает фиксировать следующую, иначе он определяет, что переменная должна быть FALSE и продолжает. Таким образом, FSAT разрешима за полиномиальное время, используя оракул, решающий SAT. В общем случае, задача в NP называется самоприводимой, если её функциональный вариант можно решить за полиномиальное время, используя оракул, решающий исходную задачу. Каждая NP-полная задача является самоприводимой. Предполагается, что задача факторизации целых чисел не является самоприводимой, поскольку определение, является ли целое число простым, лежит в классе P (легко), в то время как задача факторизации целых чисел, как считается, сложна для классического компьютера. Существует несколько (несколько различающихся) понятий самоприводимости.

Проблемы с общей функцией

Отношение, используемое для определения функциональных задач, имеет недостаток неполноты: не для каждого входного значения существует соответствующее выходное значение, такое что . Следовательно, вопрос о вычислимости доказательств не отделен от вопроса об их существовании. Чтобы преодолеть эту проблему, удобно рассматривать ограничение функциональных задач на полные отношения, что приводит к классу TFNP как подклассу FNP. Этот класс включает такие задачи, как вычисление чистых равновесий Нэша в определенных стратегических играх, где гарантировано существование решения. Кроме того, если TFNP содержит хотя бы одну FNP-полную задачу, то следует, что .