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

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