Információk Cook-ról

A számítási komplexitás elméletében a probléma Cook - ra redukálása egy $R_{1}$ $R_{2}$ időben polinomiális algoritmus ( más szóval egy polinomiális futásidejű Turing-gép ), amely megoldja a problémát , feltéve, hogy a probléma megoldását megtaláló függvény. orákulumként adatik meg , vagyis a hozzá való fellebbezés csak egy lépést igényel. $R_{1}$ $R_{2}$

Ha létezik ilyen algoritmus, azt mondjuk, hogy Cooke- ra redukálható és írható $R_{1}$ $R_{2}$

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

Informálisan ebben az esetben azt mondják, hogy "legalább olyan összetett", mint a . $R_{2}$ $R_{1}$

Ha a feladatot Cook szerint a feladatra redukáljuk , akkor a feladat megoldásával a következő módon oldhatjuk meg a feladatot: amikor egy számoló algoritmust kérünk az orákulumtól, akkor a megfelelő megoldást használjuk . Mivel a Turing-gép számos alkalommal képes lekérdezni az orákulumot, a probléma megoldásának végső algoritmusa aszimptotikusan több időt vehet igénybe, mint a problémát megoldó algoritmus . $R_{1}$ $R_{2}$ $R_{2}$ $R_{1}$ $R_{1}$ $R_{2}$ $R_{1}$ $R_{2}$

Történelem

A redukálhatóság első formális meghatározását Alan Turing javasolta 1939-ben.

Lásd még

Keverés

Információk Cook-ról

Történelem

Lásd még

Linkek