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