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 zato što je notacija svođenja među problemima suptilnija s obzirom na to 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 ako je u uvjetima zadatka specificirano da se putnik vraća kući) s 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 $n$ broj bridova i $w_{i}$ težina brida $i$. Neka se reskaliraju i perturbiraju težine bridova dodjelom bridu $i$ nove težine $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 $M$. Binarnim pretraživanjem se traži najkraći Hamiltonovski put: postoji li Hamiltonovski put s težinom $<M/2$; postoji li put s težinom $<M/4$ itd. Potom, određujući težinu $W$ najkraćeg Hamiltonovskog puta, određuje se koji su bridovi na putu pitajući svaki brid $i$ postoji li Hamiltonovski put s težinom $W$ za graf izmijenjen na način da brid $i$ ima težinu $W+1$ (ako ne postoji takav put u izmijenjenom grafu, tada brid $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 s proročištem za problem u NP), i ustvari je potpun za tu klasu.