רדוקציה חישובית

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

במדעי המחשב, רדוקציה חישובית בין פונקציה A לפונקציה B היא פונקציה f מלאה וניתנת לחישוב מקבוצת הקלטים האפשריים של A לקבוצת הקלטים האפשריים של B, כך שלכל x מתקיים: \ A(x)=B(f(x)). אם קיימת רדוקציה כזו מ-A ל-B, נסמן זאת: \ A \le B.

אם \ A \le B ו-B ניתנת לחישוב, אזי גם A ניתנת לחישוב. ולהיפך: אם A לא ניתנת לחישוב, אזי גם B לא ניתנת לחישוב.

[עריכה] רדוקציה בין שפות

אם A ו-B הן פונקציות שמייצגות שפות, ומתקיים \ A \le B, אזי:

  • אם A ניתנת להכרעה, גם B ניתנת להכרעה.
  • אם קיימת מכונת טיורינג שמקבלת את A, אזי גם קיימת גם מכונת טיורינג שמקבלת את B.
  • \ \bar A \le \bar B.

[עריכה] ראו גם

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לויקיפדיה ולהרחיב אותו.
שפות אחרות