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

Тип вычислительной задачи

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Сокращения и полные проблемы

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

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

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

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

Всего функциональных проблем

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

Смотрите также

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

Рекомендации

1. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229.
2. Ко, К. (1983). «О самосократимости и слабой P-селективности». Журнал компьютерных и системных наук . 26 (2): 209–221.
3. Шнорр, К. (1976). «Оптимальные алгоритмы для самоприводимых задач». В С. Майклсоне и Р. Милнере, редакторах, Труды 3-го Международного коллоквиума по автоматам, языкам и программированию : 322–337.
4. Селман, А. (1988). «Натуральные самосократимые множества». SIAM Journal по вычислительной технике . 17 (5): 989–996.

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