פונקציה בוליאנית חמקנית
פונקציה בוליאנית $ \ 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 $ לעץ.
קישורים חיצוניים
- פונקציות בוליאניות חמקניות, באתר אוניברסיטת אילינוי
- עצי החלטה בוליאנים, באתר אוניברסיטת אילינוי
פונקציה בוליאנית חמקנית28655287