clasă de complexitate From Wikipedia, the free encyclopedia
Î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]
FP se definește formal după cum urmează:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.