Quais são exatamente as classes FP, FNP e TFNP?

Em seu livro Computational Complexity , Papadimitriou define FNP da seguinte forma:

Suponha que seja uma linguagem no NP . Pela Proposição 9.1, há um decidível em tempo polinomial, relação polinomialmente equilibrada tal que para todas as cadeias : Há uma seqüência com se e somente se . O problema da função associado a , denotado , é o seguinte problema computacional:R L x y R L ( x , y ) x ∈ L L F $L$$R_L$$x$$y$$R_L(x,y)$$x\in L$$L$$FL$

Dado , encontre uma string tal que se essa string existir; se essa string não existir, retorne "no".y R L ( x , y $x$$y$$R_L(x,y)$

A classe de todos os problemas de função associados como acima à linguagem no NP é chamada de FNP . FP é a subclasse resultante se considerarmos apenas problemas de função no FNP que podem ser resolvidos em tempo polinomial.

(...)

(...), chamamos um problema de no FNP total se, para cada string houver pelo menos um tal que . A subclasse de FNP que contém todos os problemas de funções totais é designada TFNP .$R$ y R ( x , y $x$$y$$R(x,y)$

Em um diagrama de venn na visão geral do capítulo, Papadimitriou implica que FP TFNP FNP .$\subseteq$ $\subseteq$

É difícil entender por que exatamente isso sustenta que FP TFNP, já que os problemas no FP não precisam ser totais por si só.$\subseteq$

Para entender melhor, eu tenho vasculhado a literatura para encontrar uma definição à prova d'água de FP , FNP e tipos, sem sucesso.

Na minha opinião (humilde), acho que há pouco (correto!) Material didático desses tópicos.

Para problemas de decisão, as classes são conjuntos de idiomas (isto é, conjuntos de strings).

Quais são exatamente as classes para problemas de função? Eles são conjuntos de relações, línguas, ...? O que é uma definição sólida?

O comentário de Emil Jerabek é um bom resumo, mas eu gostaria de salientar que existem outras classes com definições mais claras que capturam mais ou menos o mesmo conceito e esclarecem a relação entre todas essas coisas.

[Aviso: embora acreditei ter acertado as definições, algumas das coisas abaixo refletem minhas preferências pessoais - tentei esclarecer onde ficava.]

No mundo determinístico, uma classe de função é apenas uma coleção de funções (no sentido matemático usual da palavra "função", isto é, um mapa ). Ocasionalmente, queremos permitir "funções parciais", cuja saída é "indefinida" para determinadas entradas. (Equivalentemente, funções definidas em um subconjunto de vez de todas elas.)Σ $\Sigma^* \to \Sigma^*$$\Sigma^*$

Infelizmente, existem duas definições diferentes para flutuando, e até onde eu sei, elas não são equivalentes (embora sejam equivalentes "moralmente").$\mathsf{FP}$

• F P F N P , T F N $\mathsf{FP}$ (definição 1) é a classe de funções que podem ser calculadas em tempo polinomial. Sempre que você vê e não está em um contexto em que as pessoas estão falando sobre , esta é a definição que assumo.$\mathsf{FP}$$\mathsf{FNP}, \mathsf{TFNP}$

No mundo não determinístico, as coisas ficam um pouco engraçadas. Lá, é conveniente permitir "funções parciais e com vários valores". Seria natural chamar isso de relação binária , isto é, um subconjunto de . Mas, do ponto de vista da complexidade, muitas vezes é filosófica e mentalmente útil pensar nessas coisas como "funções não determinísticas". Acho que muitas dessas definições são esclarecidas pelas seguintes classes (cujas definições são completamente padronizadas, se não muito conhecidas):$\Sigma^* \times \Sigma^*$

• x x x { ( x , y ) : y  é de saída por um ramo do cálculo na entrada  x $\mathsf{NPMV}$ : A classe de "funções parciais com vários valores" computáveis ​​por uma máquina não determinística em tempo polinomial. O que isto significa é que existe uma máquina não determinística politempo e, na entrada , em cada ramificação não determinística, ela pode optar por aceitar e produzir alguma saída, ou rejeitar e não produzir saída. A saída "com vários valores" na entrada é então o conjunto de todas as saídas em todas as ramificações não determinísticas quando fornecido como entrada. Observe que este conjunto pode estar vazio; portanto, como uma "função com valores múltiplos", isso pode ser apenas parcial. Se pensarmos nisso em termos de relações binárias, isso corresponde à relação .$x$$x$$x$$\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$

• N P M V$\mathsf{NPMV}_t$ : total de "funções" em , ou seja, em cada entrada , pelo menos um ramo aceita (e, portanto, produz uma saída, por definição)$\mathsf{NPMV}$$x$

• N P M V Σ $\mathsf{NPSV}$ : funções de valor único (potencialmente parcial) em . Há alguma flexibilidade aqui, no entanto, em que várias ramificações podem aceitar, mas se qualquer ramificação aceitar, todos os ramos aceitantes devem ter a garantia de obter a mesma saída (para que realmente tenha um valor único). No entanto, ainda é possível que nenhum ramo aceite, portanto a função é apenas uma "função parcial" (isto é, não definida em todos os ).$\mathsf{NPMV}$$\Sigma^*$

• N P S V Σ * → Σ * N P S V t = F P N P ∩ C O N $\mathsf{NPSV}_t$ : funções totais de valor único em . Essas realmente são funções, no sentido usual da palavra, . É um exercício não muito difícil ver que (usando Def 1 para FP acima).$\mathsf{NPSV}$$\Sigma^* \to \Sigma^*$$\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$

Quando falamos sobre funções potencialmente com vários valores, falar sobre contenção de classes de complexidade não é mais útil: incondicionalmente, simplesmente porque não contém quaisquer "funções" com vários valores, mas funciona. Em vez disso, falamos sobre "contenção-c", denotado . Uma função (potencialmente parcial, com vários valores) refina uma função (potencialmente com valores múltiplos parciais) se: (1) para cada entrada para a qual produz alguma saída, o mesmo acontece com e (2) as saídas de são sempre um subconjunto das saídas de$\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$N P M V ⊆ c f g x g f f g N P M V N P S V N P M V ⊆ c N P S $\mathsf{NPSV}$$\mathsf{NPMV}$$\subseteq_c$$f$$g$$x$$g$$f$$f$$g$ . A pergunta correta é, então, se todos os "função" tem um refinamento. caso, escrevemos .$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$

• F : D → Σ * D ⊆ Σ * P F x ∈ D f ( x ) x ∉ $\mathsf{PF}$ (um pouco menos padrão) é a classe de funções (potencialmente parciais) computáveis ​​em poli-tempo. Ou seja, uma função ( ) está em se houver uma máquina determinística de politempo tal que, nas entradas o a máquina produz , e nas entradas a máquina não produz nenhuma saída (/ rejeita / diz "não" / da forma que desejar).$f\colon D \to \Sigma^*$$D \subseteq \Sigma^*$$\mathsf{PF}$$x \in D$$f(x)$$x \notin D$

• $\mathsf{FNP}$ é uma classe de "problemas de função" (em vez de uma classe de funções). Eu também chamaria "classe relacional", mas, na verdade, quaisquer que sejam as palavras usadas para descrevê-las, você precisará se esclarecer posteriormente, e é por isso que não sou particularmente parcial com essa definição. Para qualquer relação binária há um "problema de função" associado. O que é um problema de função? Não tenho uma definição matemática limpa da mesma maneira que faço para linguagem / função / relação; em vez disso, é definida pelo que é uma solução válida: uma solução válida para o problema da função associada a é qualquer função (potencialmente parcial) modo que se$\mathsf{FNP}$$R \subseteq \Sigma^* \times \Sigma^*$$R$$f$$(\exists y)[R(x,y)]$$f$ gera qualquer , e, de outro modo, não produz saída. é a classe de problemas de função associados às relações tais que (quando considerada como uma linguagem de pares) e é equilibrada em p. Portanto, não é uma classe de funções, nem uma classe de linguagens, mas uma classe de "problemas de função", onde "problema" aqui é definido aproximadamente em termos do que significa resolvê-lo.$y$$f$$\mathsf{FNP}$$R$$R \in \mathsf{P}$$\mathsf{FNP}$

• $\mathsf{TFNP}$ é então a classe de problemas de função em - definida por uma relação como acima - esse é total, no sentido de que para cada existe um tal que .$\mathsf{FNP}$$R$$R$$x$$y$$R(x,y)$

Para não precisar escrever coisas como "Se todo problema de função (resp., ) tiver uma solução em (resp., acordo com o acima) definição), então ... "neste contexto, utiliza-se a definição 2 de , que é:$\mathsf{FNP}$$\mathsf{TFNP}$$\mathsf{PF}$$\mathsf{FP}$$\mathsf{FP}$

• $\mathsf{FP}$ (definição 2) é a classe de problemas de função em que possuem uma solução de tempo polivalente. Pode-se supor que a solução (= função) aqui seja total, escolhendo uma string especial que não seja um válido para qualquer e tendo a função saída quando, caso contrário, não haveria válido . (Se necessário, podemos modificar a relação acrescentando cada com 1 e, em seguida, considerar a string 0; isso não altera a complexidade de nada envolvido).$\mathsf{FNP}$$y_0$$y$$x$$y_0$$y$$R$$y$$y_0$

A seguir, como essas várias definições se relacionam: (definição 2, que é o que você deve assumir porque está em um contexto em que está sendo comparado com ) é equivalente para . (def 2) é equivalente a (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}$

Além da extensa resposta de Joshua, quero acrescentar as seguintes definições de Elaine Ruch, seu Automata, Computability and Complexity .

A classe FP : Uma relação binária está em sse existe um algoritmo de tempo polinomial determinista que, dada uma entrada arbitrária , pode encontrar alguns tal que .$Q$$\mathsf{FP}$$x$$y$$(x,y) \in Q$

A Classe FNP : Uma relação binária é em sse existe um tempo polinomial determinista verificador, dado um par de entrada arbitrário , determina se . Equivalentemente, está em se houver um algoritmo de tempo polinomial não determinístico que, dada uma entrada arbitrária , possa encontrar alguns tais queF N P ( x , y ) ( x , y ) ∈ Q Q F N P x y ( x , y ) ∈ $Q$$\mathsf{FNP}$$(x,y)$$(x,y) \in Q$$Q$$\mathsf{FNP}$$x$$y$$(x,y) \in Q$

A partir dessas definições, fica claro que . Ela também fala brevemente sobre problemas fora do .F N $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$$\mathsf{FNP}$

Para mim, esse tem sido o recurso mais satisfatório que consiste em uma única página que encontrei desde há muito tempo.