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

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

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

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

שימוש נפוץ באורקלים הוא יצירת קשר בין שאלות פתוחות שונות, העוסקות בהיותן של פונקציות ניתנות לחישוב או ניתנות לחישוב בזמן ריצה פולינומי. זאת כיוון שמושג האורקל מאפשר להגדיר היררכיה בין פונקציות מהטבעיים לעצמם. פונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} נחשבת לניתנת לחישוב מתוך הפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} אם ניתן לחשב את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} , על ידי מכונת טיורינג למשל, כאשר משמשת כאורקל. הגדרה כזו יוצרת קדם-סדר על אוסף הפונקציות הנבחר. באופן הזה, כאשר נבחר בתור הקבוצה את כלל הפונקציות מהטבעיים לעצמם, ניתן להגדיר את דרגות טיורינג ואת יחס הסדר החלקי של "ניתנות לחישוב". ניתן ליצור את אותה ההגדרה גם על שפות. כמו כן, ניתן לעדן את היחס על ידי דרישה שזמן החישוב של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} מתוך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} יהיה פולינומי, לינארי וכו'. לדוגמה, עבור דרישה של זמן חישוב פולינומי ועל ידי בחירה מתאימה של אוסף הפונקציות או השפות, מתקבלת ההיררכיה הפולינומית.

אורקל ורדוקציות

קיומה של רדוקציה חישובית מפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} , היא למעשה מקרה פרטי של הטענה, לפיה קיים אלגוריתם לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} בהינתן אורקל לפונקציה . באופן דומה, משמעות קיומה של רדוקציה פולינומית מפונקציה לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} , היא למעשה קיומו של אלגוריתם בעל זמן ריצה פולינומי לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} בהינתן אורקל לפונקציה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} . לעיתים נוהגים לכנות רדוקציות במובן הרגיל בתור "רדוקציות קארפ" ולדבר גם על "רדוקציות טיורינג" כשהכוונה לאלגוריתם המחשב את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f} באמצעות אורקל ל-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} (אלגוריתם שיכול לקרוא ל-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g} פעמים רבות על קלטים רבים ושונים, להבדיל מהקריאה הבודדת של רדוקציית קארפ).

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.