Information om Cook

I teorin om beräkningskomplexitet är reduktionen av ett problem till Cook $R_{1}$ $R_{2}$ en algoritm som är polynom i tid (med andra ord en Turingmaskin med polynom körtid) som löser problemet förutsatt att funktionen som hittar lösningen på problemet ges till det som ett orakel , det vill säga en vädjan till den tar bara ett steg. $R_{1}$ $R_{2}$

Om en sådan algoritm finns säger vi att den är Cooke reducerbar till och skriv $R_{1}$ $R_{2}$

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

Informellt, i det här fallet, säger de att "minst lika komplext" som . $R_{2}$ $R_{1}$

Om problemet reduceras enligt Cook till problemet , så kan lösningen av problemet användas för att lösa problemet på följande sätt: när en algoritm som beräknar begärs från oraklet, används motsvarande lösning . Eftersom Turing-maskinen kan fråga oraklet ett stort antal gånger, kan den slutliga algoritmen för att lösa problemet ta asymptotiskt längre tid än algoritmen som löser problemet . $R_{1}$ $R_{2}$ $R_{2}$ $R_{1}$ $R_{1}$ $R_{2}$ $R_{1}$ $R_{2}$

Historik

Den första formella definitionen av reducerbarhet föreslogs av Alan Turing 1939.

Se även

Blandning

Länkar

Kurs "Introduktion till strukturell komplexitetsteori"
Cook Reduction ( engelska) på PlanetMath-webbplatsen .