אורקל (מדעי המחשב)

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בתורת החישוביות ובתורת הסיבוכיות, אורקל היא מכונה מופשטת שבאמצעותה נחקרות בעיות הכרעה. ניתן לדמות אותה לקופסה שחורה, שמחוברת למכונת טיורינג, ושיש לה יכולת להכריע בעיה מסוימת בצעד חישוב יחיד. הבעיות עשויות להיות מכל מחלקת סיבוכיות, וניתן להשתמש אף בבעיות שאינן ניתנות לחישוב כלל, כגון בעיית העצירה.

מכונת טיורינג עם אורקל היא מכונת טיורינג בעלת שני סרטים, שיש באפשרותה לתת לאורקל הוראה להחליף את הקלט שעל אחד הסרטים של המכונה בפלט החישוב של האורקל עבור אותו קלט. הוראה זו נחשבת לצעד חישוב יחיד. ניתן להגדיר גם מכונת טיורינג עם יותר מאורקל אחת, ואף עם אינסוף אורקלים.

שימוש נפוץ באורקלים, הוא יצירת קשר בין שאלות פתוחות שונות, העוסקות בהיותן של פונקציות ניתנות לחישוב או ניתנות לחישוב בזמן ריצה פולינומיאלי.

[עריכה] אורקל ורדוקציות

קיומה של רדוקציה חישובית מפונקציה $\ f$ לפונקציה $\ g$ , היא למעשה מקרה פרטי של הטענה, לפיה קיים אלגוריתם לפונקציה $\ f$ בהינתן אורקל לפונקציה $\ g$ . באופן דומה, קיומה של רדוקציה פולינומית מפונקציה $\ f$ לפונקציה $\ g$ , גוררת את קיומו של אלגוריתם בעל זמן ריצה פולינומיאלי לפונקציה $\ f$ בהינתן אורקל לפונקציה $\ g$ .