Funkcijski problem

U računskoj teoriji složenosti, funkcijski problem je problem različit od problema odluke, to jest, problem koji zahtijeva složeniji odgovor od pukog da/ne.

Istaknuti primjeri uključuju problem trgovačkog putnika, koji pita za put koji putnik treba obaviti, te problem cjelobrojne faktorizacije, koji pita za listu prostih faktora.

Funkcijski problemi su čudniji za proučavanje od problema odluke jer nemaju očitog analogona u terminima jezika, te i stoga jer je notacija svođenja među problemima suptilnija s obzirom da se treba transformirati i ulaz i izlaz.

Funkcijski problemi mogu biti razvrsatni u klase složenosti na isti način kao i problemi odluke. Na primjer, FP je skup svih funkcijskih problema koji mogu biti riješeni determinističkim Turingovim strojem u polinomnom vremenu, a FNP je skup svih funkcijskih problema koji mogu biti riješeni nedeterminističkim Turingovim strojem u polinomnom vremenu.

Za sve funkcije za koje su rješenja polinomski ograničena, postoji analogan problem odluke takav da funkcijski problem može biti riješen vremenski polinomnim Turingovim svođenjem na problem odluke. Na primjer, problem odluke analogan problemu trgovačkog putnika je sljedeći:

Za dani težinski usmjereni graf i cijeli broj K, postoji li Hamiltonovski put (ili Hamiltonovski ciklus ukoliko je u uvjetima zadatka specificirano da se putnik vraća kući) sa ukupnom težinom manjom ili jednakom K?

Za dano rješenje ovoga problema, problem se trgovačkog putnika može riješiti na sljedeći način. Neka je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} broj bridova i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_i} težina brida Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . Neka se reskaliraju i perturbiraju težine bridova dodjelom bridu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} nove težine Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w'_i = 2^{(n+1)} w_i + 2^i} . Ovo ne mijenja najkraći Hamiltonovski put, ali osigurava njegovu jedinstvenost. Sad se zbroje sve težine svih bridova kako bi se dobila ukupna težina Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} . Binarnim pretraživanjem se traži najkraći Hamiltonovski put: postoji li Hamiltonovski put sa težinom Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle < M/2} ; postoji li put sa težinom Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle < M/4} itd. Potom, određujući težinu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} najkraćeg Hamiltonovskog puta, određuje se koji su bridovi na putu pitajući svaki brid Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} postoji li Hamiltonovski put sa težinom Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} za graf izmjenjen na način da brid Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ima težinu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W+1} (ako ne postoji takav put u izmjenjenom grafu, tada brid Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} mora biti na najkraćem putu izvornog grafa).

Ovo smješta problem trgovačkog putnika u klasu složenosti FP ^NP (klasa funkcijskih problema koji mogu biti riješeni u polinomnom vremenu na determinističkom Turingovom stroju sa proročištem za problem u NP), i ustvari je potpun za tu klasu.