Funkcijski zadatak

U teoriji računarske kompleksnosti, problem funkcija je računski problem gde se očekuje jedan izlaz (od ukupno broja funkcija) za svaki ulaz, ali izlaz je složeniji nego problem odluke, to jest, to nije samo DA ili NE.^[1]

Formalna definicija uredi

Funkcijski problem $P$ je definisan kao relacija $R(x,y)$ preko Dekartovog proizvoda nad niskama proizvoljnog alfabeta $\Sigma$ :

$R\subset \Sigma ^{*}\times \Sigma ^{*}$

Algoritam rešava $P$ za svaki unos $x$ takav da postoji $y$ i da $(x,y)\in R$ bude zadovoljeno, pa algoritam stvara neko $y$ .

Primeri uredi

Poznat funkcijski zadatak dat je iz Funkcijskog Bulovovog problema zadovoljivosti, FSAT skraćeno. Problem, koji je usko povezan sa donošenjem problema SAT može se formulisati na sledeći način:

Data je Bulova formula $\varphi$ sa promenljivim $x_{1},\ldots ,x_{n}$ , dodeliti $x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}$ tako da je $\varphi$ jednako ${\text{TRUE}}$ ili nema dodeljivanja.

U slučaju relacije $R(x,y)$ dato je torki odgovarajuće kodiranje Bulovih formula i zadovoljavanje zadataka.

Ostali značajni primeri su problem trgovačkog putnika, koji traži za rute koje su uzete od prodavca, i problem rastavljanja na faktore, koji traži listu faktora.

Odnos prema drugim klasama složenosti uredi

Razmotriti proizvoljni problem odlučivanja u klasi NP. Po definiciji svaki problem instance $x$ gde je odgovoreno sa 'da' ima potvrdu za $y$ koja služi kao dokaz da je 'da' odgovor. Skup tih torki $(x,y)$ formira relaciju. Složenost klasa izvedena iz ove transformacije je označen $\mathbf {F} (\mathbf {NP} )$ ili FNP skraćeno. Mapiranje složenosti klase P je označeno kao FP. Klasa FP je skup problema u funkcionisanju koji se mogu rešiti pomoću determinističke Tjuringove mašine u subeksponcencijalnom vremenu, dok je FNP skup problema u funkcionisanju koji se mogu rešiti od strane ne-determinističke Tjuringove mašine u subeksponencijalnom vremenu.^[2]

Samosvesnost uredi

Obratite pažnju da problem FSAT koji je uveden iznad i može biti rešen korišćenjem samo subekspocencijalnih poziva na potprograme o kojima odlučuje SAT problem: Algoritam može prvo pitati da li je formula $\varphi$ zadovoljiva. Nakon toga algoritam može da promeni promenljivu $x_{1}$ u TAČNO i pita ponovo. Ako je rezultujuća formula zadovoljiva, algoritam $x_{1}$ prepravlja na TAČNO i nastavlja da prepravi $x_{2}$ , inače je odlučeno da $x_{1}$ mora biti lažan i nastavlja dalje. Dakle, FSAT je rešiv u subeksponencijalnom vremenu koristeći proročku mašinu o kojoj odlučuje SAT. U principu, problem NP se zove samosvesni ako je njegova funkcija u stvari varijanta koja može biti rešena u subeksponencijalnom vremenu koristeći proročku mašinu za odlučujući originalni problem. Svaki NP-kompletni problem je samosvestan. Pretpostavljeno je da problem rastavljen na faktore nije samosvestan.

Redukcija i kompletni problemi uredi

Problemi funkcija se mogu redukovati slično problemima donošenja: Imajući u vidu probleme funkcije $\Pi _{R}$ i $\Pi _{S}$ kažemo da se $\Pi _{R}$ svodi na $\Pi _{S}$ ako postoji polinom vremena funkcije $f$ and $g$ tako da za sve slučajeve $x$ of $R$ i moguće opcije $y$ od $S$ , smatra se da

Ako $x$ ima $R$ -opciju, onda $f(x)$ ima $S$ -opciju.
$(f(x),y)\in S\implies (x,g(x,y))\in R.$

Stoga je moguće definisati FNP-kompletne probleme analogne NP-kompletnom problemu:

Problem $\Pi _{R}$ je FNP-kompletan ako svaki problem u FNPmože biti redukovan u $\Pi _{R}$ . Kompleksnost klase FNP-kompletni problemi su označeni sa FNP-C ili FNPC. To se poklapa sa $\mathbf {F} (\mathbf {NP} )$ . Odatle je problem FSAT isto FNP-kompletan problem, i to podrazmeva da je $\mathbf {P} =\mathbf {NP}$ ako i samo ako je $\mathbf {FP} =\mathbf {FNP}$ .

Zbir funkcijskih zadataka uredi

Relacija $R(x,y)$ koristi se za definisanje problema koji mogu da imaju nedostatak i da budu nepotpuni: nije svaki unos $x$ duplikat $y$ tako da $(x,y)\in R$ . Stoga pitanje dokaza nije odvojeno od pitanja njegovog postojanja. Da bi se prevazišao ovaj problem zgodno je razmotriti ograničavanje funkcije problema do ukupnog odnosa klase TFNP kao podklase od FNP. Ova klasa sadrži probleme kao što su izračunavanja Nešovog ekvilibrijuma u pojedinim strateškim igrama gde se garantuje da postoji rešenje. Onda je pokazano da $\mathbf {TFNP} =\mathbf {F} (\mathbf {NP} \cap {\textbf {co-NP}})$ . Pored toga, ako TFNP sadrži NP-kompletne probleme sledi da je $\mathbf {NP} ={\textbf {co-NP}}$ .

Vidi još uredi

Reference uredi

^ Raymond Greenlaw; H. James Hoover (1998). Fundamentals of the theory of computation: principles and practice. Morgan Kaufmann. str. 45-51. ISBN 978-1-55860-474-2.
^ Rich, Elaine (2008). „The problem classes FP and FNP”. Automata, computability and complexity: theory and applications. Prentice Hall. str. 689-694. ISBN 978-0-13-228806-4.

[1] Raymond Greenlaw; H. James Hoover (1998). Fundamentals of the theory of computation: principles and practice. Morgan Kaufmann. str. 45-51. ISBN 978-1-55860-474-2.

[2] Rich, Elaine (2008). „The problem classes FP and FNP”. Automata, computability and complexity: theory and applications. Prentice Hall. str. 689-694. ISBN 978-0-13-228806-4.

[1]

[2]