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

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

Формальное определение [ править ]

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

${\ Displaystyle R \ substeq \ Sigma ^ {*} \ times \ Sigma ^ {*}}$

Алгоритм решает, если для каждого входа, такого, что существует удовлетворяющее , алгоритм производит одно такое .${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ in R}$${\ 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 (х, у)}$${\ displaystyle x}$${\ displaystyle L}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle L}$

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

Самовосстановление [ править ]

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

Редукции и полные проблемы [ править ]

Проблемы функций можно уменьшить так же, как проблемы решения: Учитывая проблемы функций и мы говорим , что сводится к если существует полиномиально вычислимая функции и такие , что для всех случаев из и возможных решений о , он считает , что${\ 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}}}$

См. Также [ править ]

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

Ссылки [ править ]

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