Informații despre Cook

În teoria complexității computaționale, reducerea unei probleme la Cook $R_{1}$ $R_{2}$ este un algoritm care este polinom în timp (cu alte cuvinte, o mașină Turing cu timp de rulare polinomial) care rezolvă problema cu condiția ca funcția care găsește soluția problemei. îi este dat ca un oracol , adică un apel la ea durează doar un pas. $R_{1}$ $R_{2}$

Dacă un astfel de algoritm există, spunem că este Cooke reductibil la și scrie $R_{1}$ $R_{2}$

R_{1}\leq _{C}R_{2}.

Informal, în acest caz, ei spun că „cel puțin la fel de complex” ca . $R_{2}$ $R_{1}$

Dacă problema este redusă conform lui Cook la problemă , atunci soluția problemei poate fi utilizată pentru a rezolva problema în următorul mod: atunci când un algoritm care calculează este solicitat de la oracol, se folosește soluția corespunzătoare . Deoarece mașina Turing poate interoga oracolul de un număr mare de ori, algoritmul final pentru rezolvarea problemei poate dura mai mult timp asimptotic decât algoritmul care rezolvă problema . $R_{1}$ $R_{2}$ $R_{2}$ $R_{1}$ $R_{1}$ $R_{2}$ $R_{1}$ $R_{2}$

Istorie

Prima definiție formală a reductibilității a fost propusă de Alan Turing în 1939.

Vezi și

Amestecarea

Link -uri

Curs „Introducere în teoria complexității structurale”
Cook Reduction ( în engleză) pe site-ul PlanetMath .