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

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

דוגמה
לא כל פונקציה בוליאנית היא חמקנית. נבחן לדוגמה את הפונקציה הבאה:

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

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

במקרה כזה, שחקן ה־ מחשב למעשה  על הבנים שלו, ושחקן ה־ מחשב  עליהם.

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

הוכחה:

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

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

נניח כי קיים יריב אופטימלי עבור עצים בעלי  עלים ונוכיח קיום גם בעבור עצים בעלי  עלים.

עבור  כללי, האלגוריתם מתחיל ומברר ערך של  כלשהו. היריב יענה 0 אם הקודקוד אליו מחובר העלה הוא קודקוד  (כלומר אם השחקן הוא שחקן ), ו- 1 אם זהו קודקוד  (כלומר שחקן ).

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

מכאן, היריב ימשיך כמו היריב האופטימלי לפונקציה המושרה בלי  (שהיא בעלת  עלים). ומכאן באינדוקציה, היריב גרר עומק  לעץ.

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

קטגוריה:אלגברה בוליאנית
קטגוריה:חישוביות