Problem funkcjonalny - Function problem

W teorii złożoności obliczeniowej , A problemem funkcja jest obliczeniowa problemu gdzie jedno wyjście (z ogólnej funkcji oczekuje się) dla każdego wejścia, ale wyjście jest bardziej złożona niż w przypadku problemu decyzyjnego . W przypadku problemów z funkcjami wyjściem nie jest po prostu „tak” lub „nie”.

Formalna definicja

Problem funkcjonalny jest definiowany jako relacja nad ciągami dowolnego alfabetu : ${\displaystyle P}$${\ Displaystyle R}$ ${\ Displaystyle \ Sigma}$

${\ Displaystyle R \ subseteq \ Sigma ^ {*} \ razy \ Sigma ^ {*}}$

Algorytm rozwiązuje , jeśli dla każdego wejścia takiego , że istnieje satysfakcjonujące , algorytm wytwarza jeden taki . ${\displaystyle P}$${\displaystyle x}$${\displaystyle y}$${\ Displaystyle (x, y) \ w R}$${\displaystyle y}$

Przykłady

Dobrze znany problem funkcji jest podany przez Functional Boolean Satisfiability Problem, w skrócie FSAT . Problem, który jest ściśle związany z problemem decyzyjnym SAT , można sformułować w następujący sposób:

Biorąc pod uwagę wartość logiczną formułę ze zmiennymi , znaleźć zadanie takie, że ocenia się lub zdecydować, że nie istnieje taki przydział.${\displaystyle \varphi}$${\displaystyle x_{1},\ldots,x_{n}}$${\ Displaystyle x_ {i} \ rightarrow \ {{\ tekst {PRAWDA}} {\ tekst {FAŁSZ}} \}}$${\displaystyle \varphi}$${\ Displaystyle {\ tekst {PRAWDA}}}$

W tym przypadku relacja jest podana przez krotki odpowiednio zakodowanych formuł binarnych i spełniających przypisania. Podczas gdy algorytm SAT, zasilany formułą , musi tylko zwrócić „niezadowalający” lub „spełniający”, algorytm FSAT musi zwrócić pewne satysfakcjonujące przypisanie w tym drugim przypadku. ${\ Displaystyle R}$${\displaystyle \varphi}$

Inne godne uwagi przykłady to problem komiwojażera , który pyta o drogę, którą sprzedawca wybrał, oraz problem faktoryzacji liczb całkowitych , który pyta o listę czynników.

Związek z innymi klasami złożoności

Rozważmy arbitralny problem decyzyjny w klasie NP . Zgodnie z definicją NP , każda instancja problemu, na którą udzielono odpowiedzi „tak”, ma certyfikat o rozmiarze wielomianowym, który służy jako dowód odpowiedzi „tak”. W ten sposób zbiór tych krotek tworzy relację, reprezentującą problem funkcji „dane w , znajdź certyfikat dla ”. Ten problem jest funkcja o nazwie wariantu funkcyjny z ; należy do klasy FNP . ${\ Displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)}$${\displaystyle x}$${\ Displaystyle L}$${\displaystyle y}$${\displaystyle x}$${\ Displaystyle L}$

FNP można traktować jako analog klasy funkcji NP , ponieważ rozwiązania problemów FNP można skutecznie (tj. w czasie wielomianowym pod względem długości danych wejściowych) zweryfikować , ale niekoniecznie skutecznie znaleźć . Natomiast klasa FP , którą można traktować jako analog klasy funkcji P , składa się z problemów funkcyjnych, których rozwiązania można znaleźć w czasie wielomianowym.

Samoredukcja

Zauważ, że przedstawiony powyżej problem FSAT może być rozwiązany przy użyciu tylko wielomianowo wielu wywołań podprogramu, który rozstrzyga problem SAT : Algorytm może najpierw zapytać, czy formuła jest spełnialna. Następnie algorytm może ustawić zmienną na TRUE i zapytać ponownie. Jeśli wynikowa formuła jest nadal zadowalająca, algorytm utrzymuje stałą wartość TRUE i kontynuuje naprawianie , w przeciwnym razie decyduje, że musi być FAŁSZ i kontynuuje. Tak więc FSAT można rozwiązać w czasie wielomianowym za pomocą wyroczni decydującej SAT . Ogólnie rzecz biorąc, problem w NP nazywa się samoredukowalnym, jeśli jego wariant funkcji można rozwiązać w czasie wielomianowym za pomocą wyroczni decydującej o pierwotnym problemie. Każdy problem NP-zupełny jest samoredukowalny. Przypuszcza się, że problem faktoryzacji liczb całkowitych nie jest redukowalny samoczynnie. ${\displaystyle \varphi}$${\displaystyle x_{1}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$

Redukcje i kompletne problemy

Problemy funkcyjne mogą być zmniejszone podobnie jak problemów decyzyjnych: Biorąc pod uwagę problemy funkcyjne i mówimy, że zmniejsza się wtedy, gdy istnieje wielomianowo czas funkcje obliczalne i takie, że dla wszystkich instancji o oraz możliwych rozwiązań na to, że posiada ${\ Displaystyle \ Pi _ {R}}$${\ Displaystyle \ Pi _ {S}}$${\ Displaystyle \ Pi _ {R}}$${\ Displaystyle \ Pi _ {S}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle x}$${\ Displaystyle R}$${\displaystyle y}$${\displaystyle S}$

• Jeśli ma -rozwiązanie, to ma -rozwiązanie.${\displaystyle x}$${\ Displaystyle R}$${\displaystyle f(x)}$${\displaystyle S}$
• ${\ Displaystyle (f (x), y) \ w S \ implikuje (x, g (x, y)) \ w R.}$

Możliwe jest zatem zdefiniowanie problemów FNP-zupełnych analogicznie do problemu NP-zupełnego:

Problem jest FNP-zupełny, jeśli każdy problem w FNP można zredukować do . Klasa złożoności problemów FNP-zupełnych jest oznaczona przez FNP-C lub FNPC . Stąd problem FSAT jest również problemem FNP-zupełnym i utrzymuje, że wtedy i tylko wtedy, gdy . ${\ Displaystyle \ Pi _ {R}}$${\ Displaystyle \ Pi _ {R}}$${\ Displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ Displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Całkowite problemy funkcjonalne

Relacja używana do definiowania problemów funkcyjnych ma tę wadę, że jest niekompletna: nie każde wejście ma odpowiednik taki, że . Dlatego kwestia obliczalności dowodów nie jest oddzielona od kwestii ich istnienia. Aby przezwyciężyć ten problem, wygodnie jest rozważyć ograniczenie problemów funkcjonalnych do całkowitych relacji dających klasę TFNP jako podklasę FNP . Ta klasa zawiera problemy, takie jak obliczanie czystej równowagi Nasha w niektórych grach strategicznych, w których gwarantuje się istnienie rozwiązania. Ponadto, jeśli TFNP zawiera jakikolwiek problem FNP-zupełny , wynika z tego, że . ${\displaystyle R(x,y)}$${\displaystyle x}$${\displaystyle y}$${\ Displaystyle (x, y) \ w R}$${\ Displaystyle \ mathbf {NP} = {\ textbf {współ-NP}}}$

Zobacz też

• Problem decyzyjny
• Problem z wyszukiwaniem
• Problem liczenia (złożoność)
• Problem optymalizacji

Bibliografia