În teoria complexității computaționale, o reducere a timpului polinomial este o metodă de rezolvare a unei probleme folosind alta. Reducerile de timp polinomial sunt frecvent utilizate în teoria complexității pentru definirea atât a claselor de complexitate, cât și a problemelor complete pentru acele clase. …
Ce este considerat timp polinom?
Se spune că un algoritm este de timp polinom dacă timpul său de rulare este mărginit superioară de o expresie polinomială de dimensiunea intrării pentru algoritm, adică T(n)=O(nk) pentru o constantă pozitivă k.
De unde știi dacă ceva este un timp polinom?
3 Răspunsuri. Un algoritm este polinom (are timp de rulare polinomial) dacă pentru unele k, C>0, timpul său de rulare pe intrări de dimensiunea n este cel mult Cnk. În mod echivalent, un algoritm este polinom dacă pentru unele k>0, timpul său de rulare pe intrări de dimensiunea n este O(nk).
Ce se întâmplă dacă reducerea este permisă în timp exponențial?
Dacă reducerea este permisă în timp exponențial, atunci poate rezolva pe deplin problema inițială și poate produce o instanță trivială a problemei țintă Aceasta înseamnă că fiecare problemă din NP este reductibilă la fiecare altă problemă prin astfel de reduceri, astfel încât fiecare problemă din NP este NP-completă pentru reduceri exponențiale de timp.
Ce este un algoritm exponențial?
Se spune că un algoritm este timp exponențial, dacă T(n) este mărginit superior de 2poly( ) , unde poli(n) este un polinom în n. Mai formal, un algoritm este timp exponențial dacă T(n) este mărginit de O(2nk) pentru o constantă k. Ref:Wiki.
