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

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

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

${\displaystyle R\subseteq \Сигма ^{*}\times \Сигма ^{*}.}$

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

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

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

Для данной булевой формулы с переменными найдите присваивание , которое оценивается как или решите, что такого присваивания не существует.${\displaystyle \varphi}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{i}\rightarrow \{{\text{ИСТИНА}},{\text{ЛОЖЬ}}\}}$${\displaystyle \varphi}$${\displaystyle {\text{ИСТИНА}}}$

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

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

Рассмотрим произвольную задачу принятия решения в классе NP . По определению NP , каждый экземпляр задачи , на который дан ответ «да», имеет сертификат полиномиального размера , который служит доказательством ответа «да». Таким образом, набор этих кортежей образует отношение, представляющее функциональную задачу «дано в , найти сертификат для ». Эта функциональная задача называется функциональным вариантом ; она принадлежит классу FNP .${\displaystyle L}$${\displaystyle x}$${\displaystyle у}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle L}$${\displaystyle у}$${\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 \Пи _{R}}$${\displaystyle \Пи _{С}}$${\displaystyle \Пи _{R}}$${\displaystyle \Пи _{С}}$${\displaystyle f}$${\displaystyle г}$${\displaystyle x}$${\displaystyle R}$${\displaystyle у}$${\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 \Пи _{R}}$${\displaystyle \Пи _{R}}$${\displaystyle \mathbf {P} =\mathbf {NP} }$${\displaystyle \mathbf {FP} =\mathbf {FNP} }$

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

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

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Октябрь 2015 ) ( Узнайте, как и когда удалять это сообщение )