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

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

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

Функциональная проблема определяется как отношение к строкам произвольного алфавита : ${\ 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 {ИСТИНА}}}$

В этом случае отношение задается кортежами соответствующим образом закодированных булевых формул и удовлетворяющих присваиваний. В то время как алгоритм 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 называется самовосстанавливающейся, если ее функциональный вариант может быть решен за полиномиальное время с помощью оракула, решающего исходную задачу. Всякая NP-полная задача самоприводима. Предполагается, что проблема целочисленной факторизации не является самосокращаемой. ${\ 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 (е (х), у) \ в S \ подразумевает (х, г (х, у)) \ в 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 (х, у)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ in R}$${\ Displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

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

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

использованная литература