פונקציה חשיבה

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

פונקציה חשיבה בזמן

ישנן שתי הגדרות שונות שקולות לפונקציה חשיבה בזמן:

• פונקציה $f:\mathbb {N} \to \mathbb {N}$ תיקרא חשיבה בזמן אם קיים מספר טבעי $n_{0}$ ומכונת טיורינג $M$ כך שלכל $n\geq n_{0}$ בהינתן הקלט $1^{n}$ תעצור לאחר בדיוק $f(n)$ צעדים.
• פונקציה $f:\mathbb {N} \to \mathbb {N}$ תיקרא חשיבה בזמן אם קיימת מכונת טיורינג $M$ בעלת שני סרטים, סרט קלט לקריאה בלבד וסרט עבודה, כך שבהתקבל קלט $1^{n}$ (היצוג של $n$ בבסיס אונרי) תשאיר על סרט העבודה בסוף הריצה את הייצוג של $f(n)$ בבסיס בינארי, בסיבוכיות זמן של $O\left(f\left(n\right)\right)$ צעדים (ניתן גם להשתמש ביצוג אונרי במקום זאת, היות שניתן לעבור בין השניים בזמן $O\left(f\left(n\right)\right)$).

פונקציה חשיבה במקום

באופן זהה, פונקציה $f:\mathbb {N} \to \mathbb {N}$ תיקרא חשיבה במקום אם קיימת מכונת טיורינג $M$ כך שבהינתן המחרוזת $1^{n}$ תדפיס את היצוג הבינארי של $f(n)$ בסיבוכיות מקום של $O\left(f\left(n\right)\right)$ תאי סרט.

דוגמאות

רוב הפונקציות השימושיות (כמו הפונקציות הלינאריות והפונקציות המעריכיות) הן חשיבות בזמן ובמקום. לא קיימת פונקציה שהיא $o(n)$ (תת לינארית) וחשיבה בזמן, אלא אם כן היא קבועה החל ממקום מסוים, היות שאין מספיק זמן לקרוא את כל הקלט. לעומת זאת, קיימות מספר רב של פונקציות תת לינאריות חשיבות במקום.

דוגמאות לפונקציות חשיבות בזמן ובמקום (כאשר $a,b\in \mathbb {N}$):

• הפונקציות הלינאריות, $an+b$
• הפולינומים, למשל $x^{2}+6x+8$
• הפונקציות המעריכיות, $a^{n}$
• פונקציית העצרת, $n!$
• $n^{n}$

דוגמאות לפונקציות חשיבות במקום:

• שורש ריבועי - $\lfloor {\sqrt {n}}\rfloor$
• שורש כללי - $\lfloor {\sqrt[{a}]{n}}\rfloor$
• לוגריתם - $\lfloor \log {n}\rfloor$

שימושים

נעשה שימוש רב בפונקציות חשיבות בזמן כנגזרת של משפטי ההירככיה. הן חשובות היות שהוכחת הההיררכיה מסתמכת על יצירת מכונת טיורינג שמכריעה האם מכונת טיורינג אחרת משתמשת ביותר מ$O\left(f\left(n\right)\right)$ מקום או זמן. זה כמובן לא אפשרי בלי היכולת לחשב את $f(n)$ בזמן או במקום זה. כך למשל נקבל ש-${\mbox{DTIME}}\left(n^{2}\right)\subsetneq {\mbox{DTIME}}(n^{3})$ או ${\mbox{NSPACE}}\left(\log ^{2}{n}\right)\subsetneq {\mbox{NSPACE}}({\sqrt {n}})$.

קישורים חיצוניים

• פונקציה חשיבה, באתר MathWorld (באנגלית)

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