אורקל (מדעי המחשב) – הבדלי גרסאות

קיומה של [[רדוקציה חישובית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>, היא למעשה מקרה פרטי של הטענה, לפיה קיים אלגוריתם לפונקציה <math>\ f</math> בהינתן אורקל לפונקציה <math>\ g</math>. באופן דומה, משמעות קיומה של [[רדוקציה פולינומית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>, היא למעשה קיומו של אלגוריתם בעל [[זמן ריצה פולינומי]] לפונקציה <math>\ f</math> בהינתן אורקל לפונקציה <math>\ g</math>. לעתים נוהגים לכנות רדוקציות במובן הרגיל בתור "רדוקציות קארפ" ולדבר גם על "רדוקציות טיורינג" כשהכוונה לאלגוריתם המחשב את <math>\ f</math> באמצעות אורקל ל-<math>\ g</math> (אלגוריתם שיכול לקרוא ל-<math>\ g</math> פעמים רבות על קלטים רבים ושונים, להבדיל מהקריאה הבודדת של רדוקציתרדוקציית קארפ).