פונקציה בוליאנית חמקנית

פונקציה בוליאנית $\ f$ על $\ n$ משתנים, נקראת חמקנית (evasive) אם זמן הריצה של כל אלגוריתם עץ הכרעה עבורה הוא בדיוק $\ n$. או במילים אחרות, כל אלגוריתם שמחשב את $\ f$, צריך להעריך את כל $\ n$ ביטי הקלט במקרה הגרוע ביותר.

דוגמה

לא כל פונקציה בוליאנית היא חמקנית. נבחן לדוגמה את הפונקציה הבאה: $\ (x_{0}\land x_{2})\lor ({\bar {x_{0}}}\land x_{1})$ הפונקציה תלויה בשלושת המשתנים שלה: $\ x_{0},x_{1},x_{2}$, אבל מספיק לשאול רק שתי שאלות כדי להעריך אותה: נגלה תחילה את הערך של $\ x_{0}$. אם $\ x_{0}$ הוא אמת, נברר את הערך של $\ x_{2}$ ונחזיר אותו כערך כל הפונקציה, ואם הערך של $\ x_{0}$ הוא שקר, נברר את הערך של $\ x_{1}$ ונחזיר אותו כערך כלל הפונקציה.

פונקציות הערכה בעצי משחק

נבחן מקרה פרטי של עצי משחק, בו הערכים האפשריים לקודקודים הם 0 ו-1.

במקרה כזה, שחקן ה $\ max$ מחשב למעשה $\ \lor$ על הבנים שלו, ושחקן ה $\ \min$ מחשב $\ \land$ עליהם.

משפט: עבור עץ משחק כפי שתואר, בעל $\ n$ עלים, פונקציית ההערכה שלו היא חמקנית.

הוכחה:

נוכיח באינדוקציה על $\ n$ שישנו יריב אופטימלי שגורר עומק $\ n$ לעץ ההכרעה.

עבור $\ n=1$ עלים, האלגוריתם יהיה חייב לברר את ערכו של העלה היחיד, ובמקרה זה לא משנה מה היריב יענה.

נניח כי קיים יריב אופטימלי עבור עצים בעלי $\ n-1$ עלים ונוכיח קיום גם בעבור עצים בעלי $\ n$ עלים.

עבור $\ n$ כללי, האלגוריתם מתחיל ומברר ערך של $\ x_{i}$ כלשהו. היריב יענה 0 אם הקודקוד אליו מחובר העלה הוא קודקוד $\ \lor$ (כלומר אם השחקן הוא שחקן $\ max$), ו- 1 אם זהו קודקוד $\ \land$ (כלומר שחקן $\ min$).

הערך שהיריב ענה לא גרם לתשובה חד-משמעית בעבור הקודקוד - במקרה של קודקוד $\ \lor$ העובדה שאחד הערכים הוא 0 לא קובעת את ערך הקודקוד וכך גם בעבור קודקוד $\ \land$ בו ידוע שאחד הערכים הוא 1. בכל מקרה השחקן שמשחק את הקודקוד יאלץ לברר את ערכי שאר הבנים.

מכאן, היריב ימשיך כמו היריב האופטימלי לפונקציה המושרה בלי $\ x_{i}$ (שהיא בעלת $\ n-1$ עלים). ומכאן באינדוקציה, היריב גרר עומק $\ n$ לעץ.

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

• פונקציות בוליאניות חמקניות, באתר אוניברסיטת אילינוי
• עצי החלטה בוליאנים, באתר אוניברסיטת אילינוי