Функциональная проблема

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

Формальное определение

Функциональная проблема $P$ определяется соотношением $R$ над строками произвольного алфавита $\Sigma$:

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}.$

Алгоритм решает $P$ если для каждого входа $x$ такой, что существует $y$ удовлетворяющий $(x,y)\in R$, алгоритм выдает один такой $y$, а если таких нет $y$, он отклоняет.

Задаче функции обещания разрешено делать что угодно (поэтому она не может завершиться), если нет такой задачи. $y$ существует.

Примеры

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

Дана булева формула $\varphi$ с переменными $x_{1},\ldots ,x_{n}$, найти задание $x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}$ такой, что $\varphi$ оценивается как ${\text{TRUE}}$ или решить, что такого назначения не существует.

В этом случае отношение $R$ задается кортежами соответствующим образом закодированных логических формул и удовлетворяющих присваиваний.В то время как алгоритм SAT, основанный на формуле $\varphi$, нужно только возвращать «невыполнимо» или «выполнимо», в последнем случае алгоритм FSAT должен возвращать некоторое удовлетворяющее присваивание.

Другие известные примеры включают задачу коммивояжера , в которой запрашивается маршрут, пройденный продавцом, и задачу факторизации целых чисел , в которой запрашивается список факторов.

Связь с другими классами сложности

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

FNP можно рассматривать как аналог NP функционального класса , в котором решения проблем FNP могут быть эффективно (т. е. за полиномиальное время с точки зрения длины входных данных) проверены , но не обязательно эффективно найдены . Напротив, класс FP , который можно рассматривать как аналог функционального класса P , состоит из функциональных задач, решения которых можно найти за полиномиальное время.

Самосократимость

Обратите внимание, что проблема FSAT, представленная выше, может быть решена, используя только полиномиальное число вызовов подпрограммы, которая решает проблему SAT : Алгоритм может сначала спросить, соответствует ли формула $\varphi$ является удовлетворительным. После этого алгоритм может исправить переменную $x_{1}$ выберите TRUE и спросите еще раз. Если полученная формула по-прежнему выполнима, алгоритм сохраняет $x_{1}$ зафиксировано в TRUE и продолжает исправлять $x_{2}$, в противном случае он решает, что $x_{1}$ должно быть ЛОЖЬ и продолжается. Таким образом, FSAT разрешима за полиномиальное время с использованием оракула, решающего SAT . В общем, проблема в NP называется самосократимой , если ее функциональный вариант может быть решен за полиномиальное время с помощью оракула, решающего исходную задачу. Любая NP-полная задача саморедуцируема. Предполагается, что что проблема факторизации целых чисел не является самосократимой, поскольку решение о том, является ли целое число простым, находится в P (легко), в то время как задача целочисленной факторизации считается сложной для классического компьютера.Существует несколько (немного отличающихся) понятий самосократимости.

Сокращения и полные задачи

Функциональные проблемы можно уменьшить так же, как и проблемы принятия решений: заданные функциональные проблемы $\Pi _{R}$ и $\Pi _{S}$ мы говорим это $\Pi _{R}$ сводится к $\Pi _{S}$ если существуют функции, вычислимые за полиномиальное время $f$ и $g$ такой, что для всех случаев $x$ из $R$ и возможные решения $y$ из $S$, он утверждает, что

• Если $x$ имеет $R$-решение, то $f(x)$ имеет $S$-решение.
• $(f(x),y)\in S\implies (x,g(x,y))\in R.$

Следовательно, можно определить FNP-полные задачи, аналогичные NP-полной задаче:

Проблема $\Pi _{R}$ является FNP-полной , если каждую задачу из FNP можно свести к $\Pi _{R}$. Класс сложности FNP-полных задач обозначается FNP-C или FNPC . Следовательно, задача FSAT также является FNP-полной задачей и справедливо равенство $\mathbf {P} =\mathbf {NP}$ тогда и только тогда, когда $\mathbf {FP} =\mathbf {FNP}$.

Всего проблем с функциями

Отношение $R(x,y)$ используемый для определения функциональных проблем, имеет тот недостаток, что он является неполным: не каждый ввод $x$ имеет аналог $y$ такой, что $(x,y)\in R$. Поэтому вопрос о вычислимости доказательств не отделен от вопроса об их существовании. Чтобы преодолеть эту проблему, удобно рассмотреть ограничение функциональных задач на полные отношения, в результате чего класс TFNP становится подклассом FNP . Этот класс содержит такие задачи, как вычисление чистого равновесия Нэша в некоторых стратегических играх, где гарантированно существует решение. Кроме того, если TFNP содержит какую-либо FNP-полную задачу, отсюда следует, что $\mathbf {NP} ={\textbf {co-NP}}$.

См. также

• Проблема решения
• Проблема с поиском
• Задача на счет (сложность)
• Проблема оптимизации

Ссылки

• Рэймонд Гринлоу, Х. Джеймс Гувер, Основы теории вычислений: принципы и практика , Морган Кауфманн, 1998, ISBN   1-55860-474-X , стр. 45-51
• Элейн Рич , Автоматы, вычислимость и сложность: теория и приложения , Прентис Холл, 2008, ISBN   0-13-228806-0 , раздел 28.10 «Задачи классов FP и FNP», стр. 689–694.