Problemă de funcționare

În teoria complexității de calcul , o problemă funcțională este o problemă de calcul în care este așteptată o singură ieșire (a unei funcții totale ) pentru fiecare intrare, dar ieșirea este mai complexă decât cea a unei probleme de decizie , adică nu este doar „DA " sau nu". Exemple remarcabile includ problema vânzătorului călător , care necesită ruta luată de vânzătorul călător, și problema factorizării întregi , care necesită o listă de factori.

Problemele de funcționare sunt mai complicate de studiat decât problemele de decizie, deoarece nu au un analog evident în ceea ce privește limbajele și pentru că noțiunea de reducere a problemei este mai subtilă prin faptul că trebuie să transformăm ieșirea, precum și intrarea. Problemele de funcționare pot fi sortate în clase de complexitate la fel ca problemele de decizie. De exemplu, FP este setul de probleme funcționale care pot fi rezolvate de o mașină Turing deterministă în timp polinomial , iar FNP este setul de probleme funcționale care pot fi rezolvate de o mașină Turing nedeterministă în timp polinomial .

Pentru toate problemele funcționale pentru care soluția este delimitată polinomial, există o problemă de decizie analogă, astfel încât problema funcției poate fi rezolvată prin reducerea Turing a timpului polinomial la acea problemă de decizie. De exemplu, problema deciziei analogă cu problema vânzătorului călător este următoarea:

Având în vedere un grafic direct ponderat și un număr întreg K, există o cale Hamiltoniană (sau ciclul hamiltonian dacă funcționarul trebuie să se întoarcă acasă) cu o greutate totală mai mică sau egală cu K?

Având o soluție la această problemă, putem rezolva problema vânzătorului călător după cum urmează. Este $n$ ${\ displaystyle n}$ $n$ numărul muchiilor și ambele $w_{i}$ ${\ displaystyle w_ {i}}$ $w_ {i}$ greutatea muchiei $the$ ${\ displaystyle i}$ $the$ . Mai întâi re-proporționăm și perturbăm greutățile marginilor atribuindu-le marginii $the$ ${\ displaystyle i}$ $the$ noua greutate $w'_{i}=2^{(n+1)}w_{i}+2^{i}$ ${\ displaystyle w '_ {i} = 2 ^ {(n + 1)} w_ {i} + 2 ^ {i}}$ ${\ displaystyle w '_ {i} = 2 ^ {(n + 1)} w_ {i} + 2 ^ {i}}$ . Acest lucru nu schimbă cea mai scurtă cale Hamiltoniană, dar asigură faptul că este unică. Acum adăugați greutățile tuturor muchiilor pentru a obține o greutate totală $M.$ ${\ displaystyle M}$ $M.$ . Găsiți greutatea celei mai scurte căi hamiltoniene prin căutare binară : există o cale hamiltoniană cu greutate $<M/2$ ${\ displaystyle <M / 2}$ ${\ displaystyle <M / 2}$ ; există o cale cu greutate $<M/4$ ${\ displaystyle <M / 4}$ ${\ displaystyle <M / 4}$ etc. Apoi, după ce am găsit greutatea $W$ ${\ displaystyle W}$ $W$ din cea mai scurtă cale Hamilton, determinați care margini sunt în cale cerând fiecare margine $the$ ${\ displaystyle i}$ $the$ dacă există o cale hamiltoniană cu greutate $W$ ${\ displaystyle W}$ $W$ pentru graficul modificat, astfel încât marginea $the$ ${\ displaystyle i}$ $the$ au greutate $W+1$ ${\ displaystyle W + 1}$ ${\ displaystyle W + 1}$ (dacă nu există o astfel de cale în graficul modificat, atunci marginea $the$ ${\ displaystyle i}$ $the$ trebuie să fie pe cea mai scurtă cale pentru graficul original).

Aceasta pune problema vânzătorului călător în clasa de complexitate FP ^NP (clasa problemelor funcționale care pot fi rezolvate în timp polinomial pe o mașină Turing deterministă cu un oracol pentru o problemă în NP) și, de fapt, este completă pentru acea clasă.

Bibliografie

Raymond Greenlaw, H. James Hoover, Fundamentele teoriei calculului: principii și practică , Morgan Kaufmann, 1998, ISBN 1-55860-474-X , pp. 45-51
Elaine Rich, Automate, calculabilitate și complexitate: teorie și aplicații , Prentice Hall, 2008, ISBN 0-13-228806-0 , secțiunea 28.10 "Clasele de probleme FP și FNP", pp. 689-694

Elemente conexe

Problema deciziei

Portal IT

Portalul de matematică