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

שימוש נפוץ באורקלים, הוא יצירת קשר בין שאלות פתוחות שונות, העוסקות בהיותן של פונקציות [[חישוביות|ניתנות לחישוב]] או ניתנות לחישוב ב[[זמן ריצה פולינומי]]. זאת כיוון שמושג האורקל מאפשר להגדיר היררכיה בין [[פונקציה|פונקציות]] מהטבעיים לעצמם. פונקציה f נחשבת לניתנת לחישוב מתוך הפונקציה g אם ניתן לחשב את f, על ידי מכונת טיורינג לדוגמה, כאשר g משמשת כאורקל. הגדרה כזו יוצרת [[חצי יחסקדם סדר]] על אוסף הפונקציות הנבחר. באופן הזה, כאשר נבחר בתור הקבוצה את כלל הפונקציות מהטבעיים לעצמם, ניתן להגדיר את [[דרגות טיורינג]] ואת יחס הסדר החלקי של "ניתנות לחישוב". ניתן ליצור את אותה ההגדרה גם על [[שפה (מדעי המחשב)|שפות]]. כמו כן, ניתן לעדן את היחס על ידי דרישה שזמן החישוב של f מתוך g יהיה [[פולינום|פולינומיאלי]], לינארי וכו'. לדוגמה, עבור דרישה של זמן חישוב פולינומיאלי ועל ידי בחירה מתאימה של אוסף הפונקציות או השפות, מתקבלת [[ההיררכייה הפולינומית]].