Problemă de funcționare - Function problem

În teoria complexității de calcul , o problemă de funcție 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 . Pentru probleme de funcționare, ieșirea nu este pur și simplu „da” sau „nu”.

Definiție formală

O problemă funcțională este definită ca o relație peste șirurile unui alfabet arbitrar : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

${\ displaystyle R \ subseteq \ Sigma ^ {*} \ times \ Sigma ^ {*}}$

Un algoritm rezolvă dacă pentru fiecare intrare astfel încât există o satisfacție , algoritmul produce unul astfel . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ în R}$${\ displaystyle y}$

Exemple

O problemă de funcție bine cunoscută este dată de Problema funcțională de satisfacție booleană, pe scurt FSAT . Problema, care este strâns legată de problema deciziei SAT , poate fi formulată după cum urmează:

Având în vedere o formulă booleană cu variabile , găsiți o atribuire astfel încât să evaluați sau să decideți că nu există o astfel de atribuire.${\ displaystyle \ varphi}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} \ rightarrow \ {{\ text {TRUE}}, {\ text {FALSE}} \}}$${\ displaystyle \ varphi}$${\ displaystyle {\ text {TRUE}}}$

În acest caz, relația este dată de tupluri de formule booleene codificate corespunzător și de sarcini satisfăcătoare. În timp ce un algoritm SAT, alimentat cu o formulă , trebuie doar să returneze „nesatisfăcător” sau „satisfăcător”, un algoritm FSAT trebuie să returneze o anumită misiune satisfăcătoare în acest din urmă caz. ${\ displaystyle R}$${\ displaystyle \ varphi}$

Alte exemple notabile includ problema vânzătorului călător , care solicită ruta luată de vânzător, și problema factorizării întregi , care cere lista factorilor.

Relația cu alte clase de complexitate

Luați în considerare o problemă de decizie arbitrară în clasa NP . Prin definiția NP , fiecare instanță problemă căreia i se răspunde „da” are un certificat de dimensiune polinomială care servește drept dovadă pentru răspunsul „da”. Astfel, setul acestor tupluri formează o relație, reprezentând problema funcției "dată în , găsiți un certificat pentru ". Această problemă funcțională se numește varianta funcțională a ; aparține clasei FNP . ${\ displaystyle L}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle L}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle L}$

FNP poate fi considerat analogul clasei de funcții a NP , prin faptul că soluțiile problemelor FNP pot fi verificate eficient (adică, în timp polinomial în ceea ce privește lungimea intrării) , dar nu neapărat găsite în mod eficient . În schimb, clasa FP , care poate fi considerată analogul clasei de funcții a lui P , constă în probleme funcționale ale căror soluții pot fi găsite în timp polinomial.

Auto-reducibilitate

Observați că problema FSAT introdusă mai sus poate fi rezolvată folosind doar polinomial multe apeluri către un subrutină care decide problema SAT : Un algoritm poate întreba mai întâi dacă formula este satisfăcătoare. După aceea, algoritmul poate repara variabila la TRUE și poate întreba din nou. Dacă formula rezultată este încă satisfăcătoare, algoritmul rămâne fixat la TRUE și continuă să se repare , altfel decide că trebuie să fie FALS și continuă. Astfel, FSAT este rezolvabil în timp polinomial utilizând un SAT care decide oracolul . În general, o problemă în NP se numește auto-reductibilă dacă varianta funcției sale poate fi rezolvată în timp polinomial folosind un oracol care decide problema inițială. Fiecare problemă NP-completă este auto-reductibilă. Se presupune că problema factorizării întregi nu este auto-reductibilă. ${\ displaystyle \ varphi}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$

Reduceri și probleme complete

Probleme de funcționare pot fi reduse mult ca probleme de decizie: Avand in vedere probleme de funcționare și noi spunem că reduce la dacă există polinomial timp funcții de calcul și astfel încât , pentru toate cazurile de și posibile soluții ale , ea susține că ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {S}}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle y}$${\ displaystyle S}$

• Dacă are o soluție, atunci are o soluție.${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle f (x)}$${\ displaystyle S}$
• ${\ displaystyle (f (x), y) \ în S \ implică (x, g (x, y)) \ în R.}$

Prin urmare, este posibil să se definească probleme FNP-complete analoge cu problema NP-complete:

O problemă este completată de FNP dacă fiecare problemă din FNP poate fi redusă la . Clasa de complexitate a problemelor FNP-complete este notată cu FNP-C sau FNPC . Prin urmare, problema FSAT este, de asemenea, o problemă completă FNP și susține că dacă și numai dacă . ${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ Pi _ {R}}$${\ displaystyle \ mathbf {P} = \ mathbf {NP}}$${\ displaystyle \ mathbf {FP} = \ mathbf {FNP}}$

Probleme totale de funcționare

Relația utilizată pentru a defini problemele funcționale are dezavantajul de a fi incompletă: Nu fiecare intrare are un omolog astfel încât . Prin urmare, problema calculabilității probelor nu este separată de problema existenței lor. Pentru a depăși această problemă, este convenabil să se ia în considerare restricționarea problemelor funcționale la relațiile totale care dau clasa TFNP ca o subclasă a FNP . Această clasă conține probleme cum ar fi calculul echilibrelor Nash pure în anumite jocuri strategice în care este garantată existența unei soluții. În plus, dacă TFNP conține orice problemă completă a FNP , urmează că . ${\ displaystyle R (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x, y) \ în R}$${\ displaystyle \ mathbf {NP} = {\ textbf {co-NP}}}$

Vezi si

• Problema deciziei
• Problemă de căutare
• Problemă de numărare (complexitate)
• Problemă de optimizare

Referințe