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ă
[modificare | modificare sursă]FP se definește formal după cum urmează:
- O relație binară este în FP dacă și numai dacă există un algoritm determinist în timp polinomial care, dacă i se dă , fie găsește un astfel încât este adevărat, fie semnalează că nu există un astfel de .
Clase de complexitate asociate
[modificare | modificare sursă]- 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
[modificare | modificare sursă]- ^ Bürgisser, Peter (). 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 (). „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
[modificare | modificare sursă]Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.