הלמה של יאו

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

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

לקריאה נוספת

Yao, Andrew (1977), "Probabilistic computations: Toward a unified measure of complexity", Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 222–227