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