Что такое классы FP, FNP и TFNP?

В своей книге « Вычислительная сложность» Пападимитриу определяет FNP следующим образом:

Предположим, что $L$ является языком в NP . Согласно предложению 9.1, существует многочлен время разрешимо, полиномиальные сбалансировано соотношение $R_L$ таких , что для всех строк $x$ : Существует строку $y$ с $R_L(x,y)$ , если и только если $x\in L$ . Функциональная проблема, связанная с $L$ , обозначаемая $FL$ , является следующей вычислительной задачей:

По заданному $x$ найдите строку $y$ такую, что $R_L(x,y)$ если такая строка существует; если такой строки не существует, вернуть «нет».

Класс всех функциональных проблем, связанных с языком в NP, как указано выше, называется FNP . FP является подклассом, возникающим, если мы рассмотрим только функциональные проблемы в FNP, которые могут быть решены за полиномиальное время.

(...)

(...) мы называем задачу $R$ в общем объеме FNP, если для каждой строки x найдется хотя бы один такой y , что R ( x , y ) . Подкласс FNP, содержащий все полные функциональные проблемы, обозначается TFNP .$x$$y$$R(x,y)$

В диаграмме Венна в обзоре главы Пападимитриу подразумевает, что FP $\subseteq$ TFNP $\subseteq$ FNP .

Я с трудом понимаю, почему именно FP $\subseteq$ TFNP, поскольку проблемы в FP не должны быть общими как таковые.

Чтобы лучше понять, я безуспешно пробираюсь через литературу, чтобы найти водонепроницаемое определение FP , FNP и сортов.

По моему очень (скромному) мнению, я думаю, что есть немного (правильно!) Дидактического материала по этим темам.

Для решения задач классы представляют собой наборы языков (т.е. наборы строк).

Какие именно классы для функциональных задач? Это наборы отношений, языков, ...? Что такое твердое определение?

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

[Предупреждение: хотя я считаю, что я правильно понял определения, некоторые из приведенных ниже вещей отражают мои личные предпочтения - я пытался уточнить, где это было.]

В детерминированном мире класс функций - это просто набор функций (в обычном математическом смысле слова «функция», то есть отображение ). Иногда мы хотим разрешить «частичные функции», чей вывод «неопределен» для определенных входных данных. (Эквивалентно, функции, которые определены на подмножестве Σ ∗, а не на всех.)$\Sigma^* \to \Sigma^*$$\Sigma^*$

К сожалению, существует два разных определения , и, насколько я могу судить, они не эквивалентны (хотя они «морально» эквивалентны).$\mathsf{FP}$

• (определение 1) - это класс функций, которые могут быть вычислены за полиномиальное время. Всякий раз, когда вы видите F P, а это не в контексте, когда люди говорят о F N P , T F N P , это определение, которое я предполагаю.$\mathsf{FP}$$\mathsf{FP}$$\mathsf{FNP}, \mathsf{TFNP}$

В недетерминированном мире все становится немного смешно. Там удобно разрешать «частичные, многозначные функции». Естественно было бы также назвать такую ​​вещь бинарным отношением , то есть подмножеством . Но с точки зрения сложности часто философски и умственно полезно думать об этих вещах как о «недетерминированных функциях». Я думаю, что многие из этих определений разъясняются следующими классами (чьи определения полностью стандартизированы, если не очень хорошо известны):$\Sigma^* \times \Sigma^*$

• : класс «частичных многозначных функций», вычисляемых недетерминированной машиной за полиномиальное время. Это означает, что есть недетерминированная машина с многократным использованием времени, и на входе x в каждой недетерминированной ветви она может принять решение принять и сделать некоторый вывод, либо отклонить и не делать вывод. «Многозначный» выходной сигнал на входе x представляет собой набор всех выходных данных на всех недетерминированных ветвях, если вкачестве входных данныхуказан x . Обратите внимание, что этот набор может быть пустым, поэтому как «многозначная функция» он может быть только частичным. Если мы думаем об этом в терминах бинарных отношений, это соответствует отношению { ( x , y ) : $\mathsf{NPMV}$$x$$x$$x$ .$\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$

• : Общее количество «функций» в N P M V , то есть на каждом входеxпринимает по крайней мере одна ветвь (и, следовательно, делает вывод по определению)$\mathsf{NPMV}_t$$\mathsf{NPMV}$$x$

• : однозначная (потенциально) частичные функции в N P M V . Однако здесь есть некоторая гибкость, заключающаяся втом, что несколько ветвей могут принять, но если любая ветка принимает, то все принимающие ветви должны быть гарантированно сделать один и тотжевывод (так, чтобы это действительно было однозначным). Тем не менее, все еще возможно, что ни одна ветвь не принимает, поэтому функция является только «частичной функцией» (т.е. не определена на всех из Σ ∗ ).$\mathsf{NPSV}$$\mathsf{NPMV}$$\Sigma^*$

• : Однозначная общие функции в N P S V . Это действительно функции в обычном смысле слова Σ ∗ → Σ ∗ . Это не слишком сложное упражнение, чтобы увидеть, что N P S V t = F P N P ∩ c o N P (используя Def 1 для FP выше).$\mathsf{NPSV}_t$$\mathsf{NPSV}$$\Sigma^* \to \Sigma^*$$\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$

$\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$$\mathsf{NPSV}$$\mathsf{NPMV}$$\subseteq_c$$f$$g$$x$$g$$f$$f$всегда являются подмножеством выходов . Тогда правильный вопрос заключается в том, имеет ли каждая «функция» функцию . Если это так, мы пишем .$g$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$

• $\mathsf{PF}$ (чуть менее стандартный) - это класс (потенциально частичных) функций, вычислимых в поли-времени. То есть, функция ( ) находится в , если есть поли-времени детерминированной машины таким образом , что на входах машина выводит , а на входы машина не выводит (/ отклоняет / говорит «нет» / как бы вы ни хотели это ).$f\colon D \to \Sigma^*$$D \subseteq \Sigma^*$$\mathsf{PF}$$x \in D$$f(x)$$x \notin D$

• $\mathsf{FNP}$ - это класс «функциональных проблем» (а не класс функций). Я бы также назвал «реляционным классом», но на самом деле, какие бы слова вы ни использовали для его описания, вам нужно прояснить себя позже, поэтому я не особенно неравнодушен к этому определению. С любым бинарным отношением связана «функциональная проблема». Что такое функциональная проблема? У меня нет четкого математического определения, как у языка / функции / отношения; скорее, оно определяется тем, что является допустимым решением: допустимым решением проблемы функции, связанной с является любая (потенциально частичная) функция такая, что если$\mathsf{FNP}$$R \subseteq \Sigma^* \times \Sigma^*$$R$$f$$(\exists y)[R(x,y)]$$f$ выводит любой такой , а в противном случае не выводит. - это класс функциональных задач, связанных с отношениями такой, что (если рассматривать его как язык пар) и является p-сбалансированным. Таким образом, - это не класс функций и не класс языков, а класс «функциональных проблем», где «проблема» здесь определяется примерно с точки зрения того, что означает ее решение.$y$$f$$\mathsf{FNP}$$R$$R \in \mathsf{P}$$\mathsf{FNP}$

• $\mathsf{TFNP}$Тогда является классом функциональных задач в - определяемым соотношением как указано выше - такой тотален, в том смысле, что для каждого существует такой , что .$\mathsf{FNP}$$R$$R$$x$$y$$R(x,y)$

Чтобы не приходилось писать такие вещи, как «Если каждая функция (соответственно, )» имеет решение в (соответственно, согласно вышеописанному определение), затем ... "в этом контексте используется определение 2 из , а именно:$\mathsf{FNP}$$\mathsf{TFNP}$$\mathsf{PF}$$\mathsf{FP}$$\mathsf{FP}$

• $\mathsf{FP}$ (определение 2) - это класс функциональных задач в которые имеют решение по времени. Можно предположить, что решение (= функция) здесь является полным, выбрав специальную строку которая не является допустимой для любого , и имея функцию, когда в противном случае не было бы допустимого . (При необходимости мы можем изменить отношение , добавляя перед каждым 1, а затем принимать в качестве строки 0; это не меняет сложности чего-либо вовлеченного).$\mathsf{FNP}$$y_0$$y$$x$$y_0$$y$$R$$y$$y_0$

Вот как эти различные определения связаны друг с другом, (определение 2, что вы и должны предполагать, поскольку оно находится в контексте, где его сравнивают с ), эквивалентно to . (def 2) эквивалентно (def 1).$\mathsf{FNP} \subseteq \mathsf{FP}$$\mathsf{FNP}$$\mathsf{NPMV} \subseteq_c \mathsf{PF}$$\mathsf{TFNP} \subseteq \mathsf{FP}$$\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$

В дополнение к обширному ответу Джошуа, я хочу добавить следующие определения от Элейн Рух, ее автоматов, вычислимости и сложности .

Класс ФП : Бинарное отношение в тогда и только тогда существует детерминированный полиномиальный алгоритм времени , что, учитывая произвольный входной , можно найти таких , что .$Q$$\mathsf{FP}$$x$$y$$(x,y) \in Q$

Класс ФНП : Бинарное отношение в тогда и только тогда существует детерминированный полиномиальный время верификатор, задана произвольная входная пара , определяет , является ли . Эквивалентно, находится в если существует недетерминированный полиномиальный алгоритм времени, который при произвольном входе может найти некоторый такой, что$Q$$\mathsf{FNP}$$(x,y)$$(x,y) \in Q$$Q$$\mathsf{FNP}$$x$$y$$(x,y) \in Q$

Из этих определений ясно, что . Она также кратко рассказывает о проблемах за пределами .Р Н $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$$\mathsf{FNP}$

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