Czym dokładnie są klasy FP, FNP i TFNP?

W swojej książce Computational Complexity Papadimitriou definiuje FNP w następujący sposób:

Załóżmy, że jest językiem w NP . Propozycja według 9.1 jest rozstrzygalne wielomianowego razem wielomianowo zrównoważony stosunek R L takie, że dla wszystkich ciągów x : jest łańcuch Y z R L ( x , y ) , wtedy i tylko wtedy, gdy x ∈ l . Problem funkcji związany z L , oznaczony F L , jest następującym problemem obliczeniowym:$L$$R_L$$x$$y$$R_L(x,y)$$x\in L$$L$$FL$

Biorąc pod uwagę $x$ , znajdź ciąg $y$ taki, że $R_L(x,y)$ jeśli taki ciąg istnieje; jeśli taki ciąg nie istnieje, zwróć „nie”.

Klasa wszystkich problemów funkcji związanych jak wyżej z językiem w NP nazywa się FNP . FP jest podklasą powstałą, jeśli weźmiemy pod uwagę tylko problemy funkcji w FNP, które można rozwiązać w czasie wielomianowym.

(...)

(...), nazywamy problemem $R$ w FNP sumie jeśli każdy ciąg $x$ jest co najmniej jeden $y$ takie, że $R(x,y)$ . Podklasę FNP zawierający wszystkie łączne problemy funkcyjnych oznacza się TFNP .

Na schemacie Venna w przeglądzie rozdziałów Papadimitriou sugeruje, że FP $\subseteq$ TFNP $\subseteq$ FNP .

Trudno mi zrozumieć, dlaczego dokładnie utrzymuje, że FP $\subseteq$ TFNP, ponieważ problemy w FP nie muszą być same w sobie całkowite.

Aby uzyskać lepsze zrozumienie, przeszukiwałem literaturę, aby znaleźć wodoodporną definicję FP , FNP i gatunków, bez powodzenia.

Moim bardzo (skromnym) zdaniem uważam, że niewiele (słusznie!) Materiałów dydaktycznych na te tematy.

W przypadku problemów decyzyjnych klasy są zestawami języków (tj. Zestawami ciągów znaków).

Jakie dokładnie są klasy dla problemów funkcji? Czy są to zbiory relacji, języków, ...? Co to jest solidna definicja?

Komentarz Emila Jerabka jest miłym podsumowaniem, ale chciałem zwrócić uwagę, że istnieją inne klasy z jaśniejszymi definicjami, które wychwytują mniej więcej tę samą koncepcję i wyjaśniają związek między tymi wszystkimi rzeczami.

[Ostrzeżenie: chociaż wydaje mi się, że mam odpowiednie definicje, niektóre z poniższych rzeczy odzwierciedlają moje osobiste preferencje - starałem się wyjaśnić, gdzie to było.]

W świecie deterministycznym klasa funkcji jest tylko zbiorem funkcji (w zwykłym matematycznym znaczeniu słowa „funkcja”, czyli mapa ). Czasami chcemy zezwolić na „funkcje częściowe”, których dane wyjściowe są „niezdefiniowane” dla niektórych danych wejściowych. (Odpowiednio funkcje zdefiniowane w podzbiorze Σ ∗ zamiast w całości).$\Sigma^* \to \Sigma^*$$\Sigma^*$

Niestety, istnieją dwa różne definicje dla pływających wokół, io ile mogę powiedzieć, że nie są równoważne (choć są one „moralnie” odpowiednik).$\mathsf{FP}$

• (definicja 1) to klasa funkcji, które można obliczać w czasie wielomianowym. Ilekroć widzisz F P, a nie w kontekście, w którym ludzie mówią o F N P , T F N P , to jest to definicja, którą zakładam.$\mathsf{FP}$$\mathsf{FP}$$\mathsf{FNP}, \mathsf{TFNP}$

W niedeterministycznym świecie sprawy stają się trochę zabawne. Tam wygodnie jest zezwolić na „częściowe, wielowartościowe funkcje”. Naturalne byłoby również nazwanie takiej rzeczy relacją binarną , czyli podzbiorem . Ale z punktu widzenia złożoności często filozoficznie i mentalnie przydatne jest myślenie o tych rzeczach jako o „funkcjach niedeterministycznych”. Myślę, że wiele z tych definicji zostało wyjaśnionych przez następujące klasy (których definicje są całkowicie znormalizowane, jeśli nie bardzo dobrze znane):$\Sigma^* \times \Sigma^*$

• $\mathsf{NPMV}$$x$$x$$x$$\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$

• $\mathsf{NPMV}_t$$\mathsf{NPMV}$$x$

• $\mathsf{NPSV}$$\mathsf{NPMV}$$\Sigma^*$

• $\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$są zawsze podzbiorem danych wyjściowych . Właściwym pytaniem jest to czy każdy „funkcja” ma wyrafinowania. Jeśli tak, piszemy .$g$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$

• $\mathsf{PF}$ (nieco mniej standardowy) to klasa funkcji (potencjalnie częściowych) obliczalna w czasie wielozakresowym. Oznacza to, że funkcja ( ) jest , jeżeli jest poli czasie deterministyczny maszyny tak, że na wejściach wyjścia maszynowe , a na wejściach maszyna nie generuje danych wyjściowych (/ odrzuca / mówi „nie” / jakkolwiek chcesz to sformułować).$f\colon D \to \Sigma^*$$D \subseteq \Sigma^*$$\mathsf{PF}$$x \in D$$f(x)$$x \notin D$

• $\mathsf{FNP}$ to klasa „problemów funkcji” (a nie klasa funkcji). Nazwałbym też „klasą relacyjną”, ale tak naprawdę, niezależnie od tego, jakich słów użyjesz do jej opisania, musisz się później wyjaśnić, dlatego nie jestem szczególnie stronniczy w tej definicji. Z dowolną relacją binarną wiąże się „problem funkcji”. Co to jest problem z funkcją? Nie mam jasnej definicji matematycznej tak, jak robię to dla języka / funkcji / relacji; jest to raczej zdefiniowane przez to, co jest poprawnym rozwiązaniem: poprawnym rozwiązaniem problemu funkcji związanego z jest dowolna (potencjalnie częściowa) funkcja taka, że ​​jeśli$\mathsf{FNP}$$R \subseteq \Sigma^* \times \Sigma^*$$R$$f$$(\exists y)[R(x,y)]$$f$ generuje dowolne takie , a w przeciwnym razie nie generuje żadnych wyników. to klasa problemów funkcji związanych ze stosunkami takich że (gdy jest uważany za język par) i jest zrównoważony p. Tak więc nie jest klasą funkcji ani klasą języków, ale klasą „problemów funkcji”, w których „problem” jest tutaj zdefiniowany z grubsza pod względem tego, co oznacza jego rozwiązanie.$y$$f$$\mathsf{FNP}$$R$$R \in \mathsf{P}$$\mathsf{FNP}$

• $\mathsf{TFNP}$ to klasa problemów funkcji w - zdefiniowana przez relację jak powyżej - takie jest całkowite, w tym sensie, że dla każdego istnieje takie, że .$\mathsf{FNP}$$R$$R$$x$$y$$R(x,y)$

Aby nie musieć pisać rzeczy typu „Jeśli każdy funkcja (odpowiednio. ) problem ma rozwiązanie w (odpowiednio. zgodnie z powyższym definicja), a następnie ... ”w tym kontekście stosuje się definicję 2 z , czyli:$\mathsf{FNP}$$\mathsf{TFNP}$$\mathsf{PF}$$\mathsf{FP}$$\mathsf{FP}$

• $\mathsf{FP}$ (definicja 2) to klasa problemów funkcji w które mają rozwiązanie wielogodzinne. Można założyć, że rozwiązanie (= funkcja) jest tutaj całkowite, wybierając specjalny ciąg który nie jest prawidłowy dla dowolnego , i posiadając funkcję wyjściową gdy inaczej nie byłoby prawidłowego . (W razie potrzeby, możemy zmodyfikować relację przez poprzedzenie każdego z 1, a następnie podjąć się ciąg 0, to nie zmienia niczego związanego złożoności).$\mathsf{FNP}$$y_0$$y$$x$$y_0$$y$$R$$y$$y_0$

Oto jak te różne definicje odnoszą się do siebie, (definicja 2, którą należy przyjąć, ponieważ jest w kontekście, w którym jest porównywana z ) jest równoważna do . (def 2) jest równoważne (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}$

Oprócz obszernej odpowiedzi Jozuego, chcę dodać następujące definicje z Elaine Ruch jej Automaty, Obliczalności i Złożoności .

Klasa FP : binarna stosunek w IFF istnieje deterministyczną wielomianowej algorytm razem, biorąc pod uwagę dowolny wejściowy można znaleźć takie, że .$Q$$\mathsf{FP}$$x$$y$$(x,y) \in Q$

Klasa FNP : binarna stosunek w IFF istnieje deterministyczną czas wielomian weryfikatora, ponieważ dowolna para wejściowe określa się, czy . Odpowiednio, jest w iff istnieje niedeterministyczny wielomianowy algorytm czasu, który przy dowolnym wejściu może znaleźć trochę tak że$Q$$\mathsf{FNP}$$(x,y)$$(x,y) \in Q$$Q$$\mathsf{FNP}$$x$$y$$(x,y) \in Q$

Z tych definicji wynika, że . Mówi też krótko o problemach spoza .F N $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$$\mathsf{FNP}$

Dla mnie był to najbardziej satysfakcjonujący zasób, który składa się z jednej strony, którą znalazłem od dawna.