FP (clasă de complexitate)

În teoria complexității, clasa de complexitate FP este ansamblul problemelor funcție care pot fi rezolvate de o mașină Turing deterministă în timp polinomial. Este versiunea cu probleme funcție a clasei P de probleme de decizie^⁠(d). În linii mari, este clasa de funcții care poate fi eficient calculate pe calculatoarele clasice fără randomizare.

Diferența dintre FP și P este că problemele din P au răspunsuri pe un bit, da/nu, în timp ce problemele din FP pot produce orice ieșire care poate fi însă calculată în timp polinomial. De exemplu, adunarea a două numere este o problemă din FP, în timp ce a determina dacă suma lor este impară este o problemă din P.^[1]

Problemele funcție în timp polinomial sunt fundamentale în definirea reducerilor de timp polinomial^⁠(d), care sunt utilizate la rândul lor pentru a defini clasa de probleme NP-complete.^[2]

Definiție formală

FP se definește formal după cum urmează:

O relație binară

P(x,y)

este în FP dacă și numai dacă există un algoritm determinist în timp polinomial care, dacă i se dă

x

, fie găsește un

y

astfel încât

P(x,y)

este adevărat, fie semnalează că nu există un astfel de

y

.

Clase de complexitate asociate

FNP^⁠(d) este mulțimea relațiilor binare pentru care există un algoritm în timp polinomial care, date fiind x și y, verifică dacă P(x, y) este adevărat. La fel cum P și FP sunt strâns legate, NP este strâns legată de FNP. FP = FNP dacă și numai dacă P = NP.
Deoarece o mașină care utilizează spațiu logaritmic are un număr de configurații care crește cel mult polinomial, FL^⁠(d), mulțimea de probleme funcție care pot fi calculate în spațiu logaritmic, este inclusă în FP. Nu se știe dacă FL = FP; aceasta este analogă cu problema de a determina dacă clasele de decizie P și L sunt egale.

Bibliografie

^ Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0.
^ Rich, Elaine (2008). „28.10 "The problem classes FP and FNP"”. Automata, computability and complexity: theory and applications. Prentice Hall. pp. 689–694. ISBN 0-13-228806-0.

Legături externe

Complexity Zoo: FP

[1] Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0.

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

[1]

[2]