Reducerea timpului polinomial
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Se spune că un limbaj A poate fi redus în timp polinomial la limbajul B (notat cu A ≤p B ), dacă există o funcție calculabilă f în timp polinomial care permite conversia instanțelor problemei A în instanțe ale lui B, astfel încât w ∈ A ↔ f (w) ∈ B.
Această definiție este utilizată pe scară largă în teoria complexității de calcul, deoarece dacă o problemă A este reductibilă în timp polinomial la B, atunci soluțiile polinomiale ale lui B pot fi utilizate pentru a rezolva polinomial și A, deoarece compoziția polinoamelor rămâne polinomială.
Mai exact, termenul „funcție calculabilă în timp polinomial” înseamnă o funcție f: Σ * → Σ * care poate fi rezolvată de o mașină Turing de timp polinomial M oprindu-se cu doar f (w) pe bandă, după ce începe cu orice w în intrare.
