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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

פונקציה בוליאנית $ \ 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 $ לעץ.

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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