לא מדויק

כיצד אורקלים מנבאים שקשה להוכיח ש-P שונה מ-NP

31 באוגוסט, 2010

בפוסט הקודם נפנפתי קצת ידיים על אחת מהסיבות הנפוצות לקושי שבהוכחה ש- $\mbox{P\ensuremath{\ne}\ensuremath{\mbox{NP}}}$ ; העובדה שאחד מרעיונות ההוכחה החזקים והיפים שבמתמטיקה ומדעי המחשב, הלכסון שגורם להפניה עצמית, מה שמככב במשפט אי השלמות של גדל ובהוכחת אי כריעותה של בעית העצירה – רעיון זה פשוט לא יכול לעבוד כאשר עוסקים ב- $\mbox{P}$ וב- $\mbox{NP}$ . בפוסט הזה אני רוצה להיות יותר טכני ולפרט גם את האופן שבו עושים זאת, אף שאני משער שחלק מהקוראים לא יצליחו לעקוב אחרי ההוכחה עד סופה. אני מניח כאן ידע מוקדם כלשהו בתורת הסיבוכיות – ספציפית, למה אנחנו מתכוונים ב"מכונת טיורינג", ב"מכונת טיורינג אי דטרמיניסטית" וב"שפה" (אוסף של מחרוזת סופיות) – מי שאינו מכיר מושגים אלו כנראה יתקשה לעקוב אחרי ההמשך.

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

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

לא הבנתם כלום? מצויין, ההמשך עוד יותר מבלבל.

הטענה $\mbox{P}\ne\mbox{NP}$ היא בעצם הטענה "מכונות אי-דטרמיניסטיות פולינומיות יכולות לעשות משהו שמכונות דטרמיניסטיות פולינומיות לא יכולות לעשות". מה שאנו רוצים להראות הוא שאם מחזקים את שני המודלים הללו עם אורקל, אז עבור אורקל אחד המכונות כן ישתוו בכוחן, אבל עבור אורקל אחר אפשר יהיה להראות שהן לא שוות בכוחן (כלומר, להוכיח טענה דמויית $\mbox{P}\ne\mbox{NP}$ אבל על מחלקה אחרת של מכונות). החלק הקל יותר הוא להרחיב את שני המודלים כך שהם כן יהיו שווים בכוחם – פשוט צריך לתת להם אורקל למשהו שהוא כל כך חזק עד שההבדלים בכוח של שתי המכונות (אם קיימים כאלו) מתפוגגים ונעלמים. דוגמה לאורקל כזה היא אורקל שבהינתן שלשה $\left(M,x,1^{n}\right)$ של מכונה $M$ , קלט $x$ ומספר $n$ שנתון בבסיס אונרי (למה? מסיבת טכניות – יעילות של אלגוריתמים נמדדת ביחס לגודל הייצוג של קלט, ואם מייצגים מספר שלא בבסיס אונרי אז גודל הייצוג שלו הוא לוגריתמי בגודל של המספר עצמו), אומר האם $M$ עונה "כן"על $x$ תוך $2^{n}$ צעדים.

אורקל לשפה הזו מאפשר למכונה דטרמיניסטית לקבל כל שפה שמכונה אי דטרמיניסטית פולינומית יכולה לקבל: אם $M$ היא מכונה אי דטרמיניסטית פולינומית ואנו רוצים לדעת אם היא מקבלת את $x$ , אז נבקש מהאורקל תשובה עבור $\left(M^{\prime},x,1^{n}\right)$ כאשר $M^{\prime}$ היא מכונה דטרמיניסטית שמבצעת חיפוש ממצה על כל אפשרויות הריצה של $M$ על $x$ ; חיפוש ממצה שכזה לוקח זמן שהוא אקספוננציאלי באורך של $x$ , ולכן בהתאם בוחרים את $n$ להיות בערך הגודל של $x$ (מסיבות טכניות אולי יהיה צורך בקצת יותר).

אלא מה? כל מה שזה מראה הוא ש- $\mbox{NP}\subseteq\mbox{P}^{L}$ (כש- $L$ היא השפה של האורקל שלנו). אנחנו רוצים להראות ש- $\mbox{NP}^{L}\subseteq\mbox{P}^{L}$ – כלומר, שגם אחרי שמחזקים את המכונות האי-דטרמיניסטיות עם האורקל של $L$ , עדיין מכונות דטרמיניסטיות מצליחות לעשות את אותם הדברים. אלא שזו לא בעיה אמיתית, כי אותה מכונה $M^{\prime}$ שמסמלצת את המכונה האי דטרמיניסטית $M$ יכולה לסמלץ גם קריאות לאורקל – כלומר, לבצע בעצמה את החישוב שהאורקל מבצע, על איזה קלט שלא יהיה ש- $M$ תזרוק עליו, ולענות במקום האורקל. זה לא יגדיל את זמן הריצה של $M^{\prime}$ בצורה משמעותית (כאן צריך לבוא נימוק טכני מפורט יותר, אך אמנע ממנו – זה תרגיל טוב לחשוב מה בדיוק צריך לומר ואיזה עוד סיבוכים עשויים לצוץ; למשל, האם $M$ יכולה לקרוא לאורקל עם קלטים שבהם $1^{n}$ הוא "גדול מדי"?).

יפה. אם כן, עבור האורקל החזק הזה, מכונת דטרמיניסטיות ואי דטרמיניסטיות משתוות. החלק הקשה יותר הוא לחשוב על אורקל שעבורו לא רק שהן לא משתוות, אלא שאפילו ניתן להוכיח זאת. במילים אחרות, אנחנו רוצים להוכיח משפט שדומה למשפט $\mbox{P}\ne\mbox{NP}$ , וצריכים לחפש את ההקלה המתאימה שתאפשר לנו להוכיח משפט שכזה.

בואו ניקח שפה $L$ כלשהי. לשפה הזו ניתן להתאים שפה אחרת, $U_{L}$ , של אורכי המילים ב- $L$ (שוב, בייצוג אונרי). במילים אחרות, בהינתן מספר $1^{n}$ השאלה היא האם קיימת מילה מאורך $n$ בשפה $L$ . זו שאלה שקל מאוד להכריע אם אנחנו מכונה אי דטרמיניסטית עם אורקל לשפה $L$ : בהינתן $n$ פשוט מנחשים מילה מאורך $n$ , שואלים את האורקל האם היא שייכת ל- $L$ ואם כן – מקבלים. אם כן, לכל שפה $L$ מתקיים ש- $U_{L}\in\mbox{NP}^{L}$ . מצד שני, מכונה דטרמיניסטית פולינומית לא יכולה לנקוט בגישה הזו – אם נותנים לה $n$ , לבדוק את כל המילים מאורך $n$ ייקח לה יותר מדי זמן כי יש $2^{n}$ כאלו. זה נותן פתח לתקווה לכך שיתקיים $U_{L}\notin\mbox{P}^{L}$ עבור שפה $L$ שתהונדס בצורה מתאימה. כמו שכל מי שמכיר קצת את תורת הסיבוכיות יודע, להוכיח שמשהו הוא קשה זה עניין קשה, והבניה של $L$ היא יצירתית למדי ומסתמכת – איך לא – על לכסון.

הבה ונמספר את כל מכונות הטיורינג הדטרמיניסטיות עם אורקל הקיימות – $M_{1},M_{2},M_{3},\dots$ . מה שנעשה יהיה לבנות את $L$ בשלבים, כשבשלב ה- $i$ ננסה לגרום למכונה $M_{i}$ לטעות בתשובה שהיא אמורה לתת על מילה כלשהי מ- $L$ .

נתחיל מכך ש- $L$ ריקה. כפי שניתן יהיה לראות מהבניה, בכל שלב תישמר התכונה שב- $L$ רק מספר סופי של מילים. בסיבוב ה- $i$ בבניה, ניקח מספר $n$ שגדול ממספר הסיבוב הנוכחי $i$ ומאורך כל המילים שעד כה הוכנסו ל- $n$ . המטרה שלנו – לגרום ל- $M_{i}$ "לטעות"בתשובה שהיא מחזירה על $1^{n}$ . בדרך כלל מה שהיינו עושים הוא לומר "נריץ את $M_{i}$ על $1^{n}$ ; אם $M_{i}$ דחתה, נוסיף את $1^{n}$ ל- $L$ ; ואם היא קיבלה לא נוסיף אותו". זה גם הרעיון כאן אבל יש לנו סיבוך – $M_{i}$ היא מכונה עם גישה לאורקל. ולא סתם אורקל – אורקל לשפה $L$ שאותה אנו בונים. כלומר, $M_{i}$ , במהלך ריצתה על $1^{n}$ , עשויה לשאול את האורקל על מילים שבכלל עוד לא החלטנו אם הן כן או לא ב- $L$ . עם זאת, זו לא בעיה של ממש – מה שנעשה הוא להריץ את $M_{i}$ על $1^{n}$ , בכל פעם שבה $M_{i}$ תשאל את האורקל על מילה שכבר החלטנו אם היא שייכת ל- $L$ או לא נענה בהתאם לבחירה שביצענו; ואם $M_{i}$ שואלת על מילה שאיננה מהמילים שכבר החלטנו עליהן, נענה (בתור האורקל) שהמילה איננה ב- $L$ ונסמן לנו את זה בצד, למקרה שגם בעתיד ישאלו על המילה הזו.

ה"סכנה" שבדרך הפעולה שלנו היא ש- $M_{i}$ עלולה לשאול את האורקל שאלה על כל המילים מאורך $n$ . זה אולי נשמע מוזר קצת בהתחלה – לא אמרנו שנדרש זמן אקספוננציאלי כדי לעשות זאת? אבל זו הנקודה העדינה המרכזית בהוכחות מהסוג הזה – אנחנו תוקפים את $M_{i}$ עבור $n$ ספציפי, בעוד שדיבורים על זמן ריצה אקספוננציאלי הם רלוונטיים רק כשמדברים על ההתנהגות האסימפטוטית של $M_{i}$ , כלומר על האופן שבו $M_{i}$ מתנהגת על אינסוף קלטים. ייתכן שעל כל הקלטים עד גודל זיליארד $M_{i}$ דורשת פרק זמן גדול עד להדהים, ורק לאחר מכן היא "נרגעת" ורצה זמן פולינומי – גם אז היא עדיין תיחשב פולינומית. מכאן שהסכנה ש- $M_{i}$ תבדוק את כל המילים מאורך $n$ היא מוחשית מאוד, ונדרשים פיתולים טכניים כדי להתגבר עליה. במקרה שלנו, פשוט נגביל את זמן הריצה של $M_{i}$ – אם היא רצה יותר מ- $\frac{2^{n}}{10}$ צעדים, פשוט נשכח ממנה ונעבור למכונה הבאה. עוד מעט אסביר איך אפשר להבטיח שזה לא יגרום נזק להוכחה שלנו.

אם $M_{i}$ עצרה על $1^{n}$ תוך לכל היותר $\frac{2^{n}}{10}$ צעדים, אז בהכרח היא לא הספיקה לשאול את האורקל על כל הקלטים מאורך $n$ . אם $M_{i}$ קיבלה, הרי שהיא טוענת שב- $L$ יש מילה מאורך $n$ , אולם כרגע בבניה שלנו אין מילה כזו. זכרו – $n$ היה מספר שגדול מאורך כל המילים שהחלטנו אם הן ב- $L$ או לא בתחילת הסיבוב $i$ , ובמהלך הסיבוב עצמו לא הוספנו אף מילה ל- $L$ – בכל פעם ש- $M_{i}$ שאלה את האורקל על מילה חדשה, אמרנו לה שאותה מילה אינה ב- $L$ . מכאן ש- $M$ טועה. אם לעומת זאת $M$ דחתה את $1^{n}$ , כלומר טענה שאין ב- $L$ מילה מאורך $n$ , פשוט נוסיף ל- $L$ מילה כלשהי ש- $M_{i}$ לא הספיקה לשאול את האורקל עליה (כאמור, יש כזו). ושוב, $M$ טועה, והגדלנו את $L$ במילה אחת בסך הכל, כך ש- $L$ עדיין סופית.

$L$ "האמיתית" היא התוצר הסופי של כל שלבי הבניה הללו. פורמלית, אם $L_{i}$ מסמנת את השפה שהתקבלה אחרי השלב ה- $i$ , אז $L=\bigcup L_{i}$ . מבחינה מתמטית זו בניה חוקית לחלוטין והשפה מוגדרת היטב, אבל היא עשויה להיות מבלבלת למדי למי שלא רגיל לדברים כאלו. עכשיו צריך להשתכנע ש- $U_{L}$ אכן אינה מתקבלת על ידי אף מכונה דטרמיניסטית פולינומית.

ובכן, נניח ש- $M$ היא מכונה דטרמיניסטית פולינומית שכזו, ושזמן הריצה שלה חסום על ידי הפולינום $p\left(n\right)$ . אז קיים $n$ גדול מספיק כך ש- $\frac{2^{n}}{10}>p\left(n\right)$ . במילים אחרות, אם ננסה "לתקוף" את $M$ עבור המילה $1^{n}$ או מילים ארוכות יותר, ננצח. איך אפשר להבטיח שאכן נתקוף את $M$ מתישהו עם מילה ארוכה שכזו? תעלול פשוט – במקום לתקוף את $M$ פעם אחת, נתקוף אותה אינסוף פעמים. כלומר, המניה $M_{1},M_{2},M_{3},\dots$ לא תכיל כל מכונה רק פעם אחת, אלא מספר אינסופי של פעמים. קל להנדס מניה שכזו – למשל, הביטו בסדרה $1,1,2,1,2,3,1,2,3,4,\dots$ שבה מובטח שכל מספר טבעי יופיע מספר אינסופי של פעמים. מכאן שאנו נתקלים ב- $M$ בתור $M_{i}$ עבור אינסוף ערכים שונים של $i$ , ומכיוון שדרשנו שה- $n$ שאותו בוחרים בסיבוב ה- $i$ יהיה בפרט גדול מ- $i$ , מובטח לנו שהחל מסיבוב מסויים ה- $n$ שאיתו נתקוף את $M$ אכן יביס אותה.

אחרי שמבינים את כל הפרטים הללו, ההוכחה הזו אינה כה מסובכת – ואכן, רוב הרעיונות בה הם סטנדרטיים לגמרי בתורת הסיבוכיות. עיקר היופי בה הוא בבניה ההדרגתית, הכמו-אלגוריתמית של $L$ ובאופן המחוכם שבו היא מצליחה להתגבר על סכנת ההפניה העצמית שנוצרת משאלות האורקל של $M_{i}$ . אבל הדבר היפה באמת בהוכחה הזו הוא בכך שההוכחה לכך שלכסון לא מסוגל לעשות דבר מה היא עצמה הוכחה בלכסון!

תגים: אורקלים, לכסון, טכני, בעיית P=NP, הוכחות יפות
שייך לקטגוריות תורת הסיבוכיות | 3 תגובות »

אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

16 באוגוסט, 2010

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

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

אזכיר אותה בקצרה (כפי שכל מי שיביט במאמר של טיורינג יראה, זה "לא בדיוק" מה שטיורינג אמר, אבל ביד חופשית שכזו נהוג להשתמש כל הזמן כל עוד לא מתיימרים לעסוק בהיסטוריה של המתמטיקה): נניח שיש לנו מכונה $Q$ שבהינתן מכונה אחרת $M$ וקלט עבורה $x$ אומרת האם $M$ עוצרת בריצתה על $x$ או שלא. כעת נבנה מכונה $U$ שעל קלט $x$ מזינה ל- $Q$ את הזוג $\left(x,x\right)$ (כלומר, שואלת את $Q$ "מה עושה המכונה המקודדת בתור $x$ כשמריצים אותה על עצמה?") ופועלת הפוך ממה ש- $Q$ אמרה – אם $Q$ אמרה ש- $x$ עוצרת על $x$ , אז $U$ נכנסת ללולאה אינסופית; ואחרת, $U$ עוצרת. בבירור ההתנהגות של $U$ כשיריצו אותה על הקלט $U$ תהיה פרדוקסלית, וזה סוף הסיפור.

ההוכחה הקצרצרה הזו מתארת אי שוויון בין מחלקות של בעיות חישוביות – במקרה הזה, בין המחלקה $\mbox{R}$ של בעיות שניתנות לפתרון, והמחלקה $\mbox{RE}$ של בעיות שניתנות לפתרון "חד צדדי"- בעיות שעבורן קיימת מכונה שעוצרת ועונה "כן" אם התשובה היא אכן כן, אך אחרת ייתכן שהיא לא תעצור כלל (או שתעצור ותגיד "לא"). אף שזה לא ברור מייד, שאלת $\mbox{P\ensuremath{\ne}NP}$ היא האנלוג הקשור ל"זמן ריצה יעיל" של תוצאת ה- $\mbox{R}\ne\mbox{RE}$ הזו. (אם לוקחים את הגדרת $\mbox{P}$ ומחלישים את הדרישה של "זמן ריצה פולינומי" על ידי החלפתה ב"זמן ריצה כלשהו, העיקר שהמכונה תעצור", מקבלים את $\mbox{R}$ ; ואם עושים את אותו הדבר ל- $\mbox{NP}$ מקבלים את $\mbox{RE}$ – זה תרגיל נחמד שאולי גם אדבר עליו פעם בבלוג).

ההוכחה הזו מחוכמת למדי – במקום לנסות ולתפוס את כל הדרכים האפשריות שבהן אפשר, אולי, להכריע את בעיית העצירה ולהראות שבכל אחת מהן יש כשל כלשהו, ההוכחה הזו הולכת בדלת האחורית – היא מניחה שאפשר להכריע את בעיית העצירה, ומראה אילו דברים אבסורדיים נובעים מכך. אם כן, מדוע לא ניתן להשתמש בהוכחה הזו גם כדי להראות ש- $\mbox{P}$ שונה מ- $\mbox{NP}$ ?

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

הרעיון בהוכחה הוא זה: אם יש לנו שתי מחלקות $A,B$ של שפות ("שפה"היא פשוט אוסף של קלטים – נניח, אוסף הקלטים שעליהם המכונה עוצרת ואומרת "כן") ואנו רוצים להראות כי $A\ne B$ , וכמו כן $A$ בבירור מוכל ב- $B$ , אז דרך אחת להראות זאת היא על ידי הצגת מכונה ששפתה נמצאת ב- $B$ , אבל היא מתנהגת באופן שונה מאשר כל מכונה ששפתה ב- $A$ . מה ה"לכסון"כאן? ובכן, זכרו שבהוכחת האלכסון של קנטור התעלול היה לבנות מספר ממשי ש"מתנהג באופן שונה" מאשר כל מספר ממשי שהיה קיים במספור של הממשיים – כלומר, הוא נבדל מכל אחד מהמספרים הללו באחד מהמקומות בפיתוח העשרוני שלהם. כאן זה אותו רעיון: אם $U$ היא המכונה שאנו בונים ו- $M$ היא מכונה כלשהי ששפתה ב- $A$ , אז יהיה קיים קלט $x$ שעליו $U$ ו- $M$ יתנהגו שונה (ובפרט לכל $M$ יהיה מדובר על $x$ אחר).

כאשר $A=\mbox{R}$ ו- $B=\mbox{RE}$ , אז המכונות ששפתן ב- $A$ הן "מכונות שעוצרות תמיד" ואילו מכונות ששפתן ב- $B$ הן "מכונות שעוצרות תמיד אם התשובה היא "כן", ואחרת יכולות לא לעצור". במילים אחרות, המכונה $U$ שנבנה יכולה לא לעצור על קלטים מסויימים, ואז מובטח שהם לא יהיו בשפה שלה.

כעת הבניה של $U$ היא פשוטה ביותר: בהינתן קלט $x$ , $U$ מפרשת אותו כמכונה $M_{x}$ , מריצה את $M_{x}$ על הקלט $x$ עצמו, ואם $M_{x}$ עצרה וענתה – היא עונה הפוך ממנה. מכיוון שכל $M$ ששפתה ב- $\mbox{R}$ מחוייבת לעצור, מובטח לנו ש- $U$ תענה הפוך מכל $M$ כזו על הקלט $\left\langle M\right\rangle$ עצמו (הסוגריים המשולשים באים לציין שמדובר על הקידוד של $M$ כמחרוזת). כמובן ש- $U$ עלולה לא לעצור כלל אם המכונה $M_{x}$ שהיא מסמלצת היא מהסוג שלא עונה אף פעם – אבל זה בסדר, כי הרשינו ל- $B$ להתנהג כך.

מכיוון שלא ממש ברור איך נראית השפה ש- $U$ מקבלת, תוצאה זו לא נותנת לנו שפה קונקרטית שלא ניתן להכריע (ועל כן ההוכחה הראשונה שהצגתי עדיפה על פניה באספקט זה) אך היא מראה כי המחלקות $\mbox{R}$ ו- $\mbox{RE}$ הן שונות; וחשוב מכך, ניתן להכליל אותה לסיטואציות רבות אחרות. אדגים כעת את אחת מהפשוטות שבהן: נניח שאנו רוצים להוכיח כי $\mbox{P\ensuremath{\ne}\ensuremath{\mbox{R}}}$ , דהיינו שיש בעיות שניתן להכריע אך אינן פתירות בזמן פולינומי – ההוכחה תעבוד כמעט באותו האופן, למעט תוספת טכנית חשובה אחת. אני מזהיר מראש – ההוכחה אינה פשוטה לגמרי וחלקכם כנראה יאבד אותי – אפשר לעבור לסוף ההוכחה בלי לפגוע מהותית בקריאת הפוסט.

שימו לב שכעת $U$ שלנו צריכה לעצור תמיד, אחרת ייתכן ששפתה לא תשתייך ל- $\mbox{R}$ . במילים אחרות, תמו ימי הנעורים הפרועים שבהם $U$ יכלה פשוט להריץ כל מכונת טיורינג עם כל קידוד שהוא, כי ייתכן שחלק מהמכונות שהיא מריצה לא יעצרו לעולם. כאן נכנס לתמונה התעלול הטכני – $U$ תפרש את הקלט $x$ כמכונה כמו קודם, אבל תריץ את $M_{x}$ על $x$ רק במשך $2^{\left|x\right|}$ צעדים – שתיים בחזקת האורך של $x$ צעדים (זכרו – $x$ היא מחרוזת). אם בפרק הזמן הזה $M_{x}$ עצרה על $x$ , הרי ש- $U$ תענה הפוך ממנה; ואחרת, פשוט תדחה. מה שאנו מתבססים עליו כאן הוא שלכל מכונה יש אינסוף קידודים מאורכים שונים ומשונים, כי תמיד אפשר להכריז שאם תו מסויים מופיע בקידוד פשוט מתעלמים ממנו (למי שזה מפריע לו – יש עוד דרכים, טיפה פחות אלגנטיות, לעקוף את הבעיה הזו).

כעת מגיע החלק המסובך – נניח שיש מכונה $M$ שפועלת בזמן ריצה פולינומי, נניח עם פולינום $p\left(n\right)$ . אז קיים $m$ טבעי כלשהו כך ש- $p\left(m\right)<2^{m}$ – זה מכיוון שפונקציה מעריכית כמו $2^{x}$ גדלה מהר יותר מכל פולינום (טענה שדורשת הוכחה אך אינה מסובכת). בואו ניקח בתור $x$ עותק של $M$ שאורכו לפחות $m$ – כעת מובטח לנו שכאשר $U$ תרוץ על $x$ היא תסמלץ את ריצת $M$ על $x$ למשך מספר צעדים כה גדול עד כי מובטח ש- $M$ תעצור על $x$ , ולכן $U$ תענה הפוך מ- $M$ . מכאן שאף מכונה פולינומית אינה מקבלת את אותה שפה בדיוק כמו $U$ , וזהו סוף הסיפור.

את ההוכחה הזו ניתן להמשיך ולשכלל, ולקבל את מה שמכונה "משפטי ההיררכייה" של תורת הסיבוכיות. הם מראים, למשל, שיש בעיות שניתן לפתור בסיבוכיות זמן $O\left(n^{2}\right)$ אך לא בסיבוכיות זמן $O\left(n\right)$ , וכדומה. אפשר להחיל את אותו רעיון גם על מחלקות סיבוכיות אי דטרמיניסטיות (הדבר דורש עוד תעלולים לא פשוטים), וישנן עוד הוכחות לכסון מחוכמות אף יותר – המפורסם ביותר מבין התוצאות המחוכמות הוא ככל הנראה משפט לדנר, שמראה שאם $\mbox{P\ensuremath{\ne}NP}$ אז קיימות "שפות ביניים" שאינן ב- $\mbox{P}$ וגם אינן $\mbox{NP}$ -שלמות, אך נעזוב את זה.

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

האם גם את $\mbox{P\ensuremath{\ne}NP}$ ניתן להוכיח בדרך זאת? נסיון נאיבי לעשות זאת ייכשל – היתרון היחיד שיש למכונות ששפתן ב- $\mbox{NP}$ על פני מכונות ב- $\mbox{P}$ הוא שהן יכולות להיות אי-דטרמיניסטיות; לא אכנס להגדרה המדוייקת של המושג (שכבר עסקתי בה בעבר) כי זה לא קריטי כרגע – הנקודה היא שעל פניו זה לא מאפשר למכונה לבצע סימולציה "עד הסוף" של כל המכונות הפולינומיות הדטרמיניסטיות; במשפטי הלכסון הקלאסיים הבעיה הזו נפתרת על ידי כך ש- $U$ רצה הרבה זמן ביחס למכונות שהיא מנסה לענות שונה מהן – כאן ל- $U$ אין שום יתרון כזה.

כמובן שבעיה אינטואיטיבית שכזו לא אמורה לעצור אף אחד. מה שעצר אנשים היה מאמר משנת 1975 של Baker-Gill-Solovay שהראה שפשוט לא ניתן להשתמש בשיטות רלטביסטיות כדי להוכיח ש- $\mbox{P\ensuremath{\ne}\mbox{NP}}$ . איך מוכיחים דבר כזה? להוכחה המדוייקת אקדיש פוסט נפרד וכעת אסתפק בתיאור הרעיון. המושג החדש שהם מכניסים לתמונה הוא זה של אורקל. אורקל, בפשטות, הוא כוח שמיימי שמסוגל לענות על שאלות מסויימות באופן מושלם ומבלי שהדבר ייקח זמן. באופן קצת יותר פורמלי מדברים תמיד על אורקל לשפות מסויימות. אורקל לשפה יכול, בהינתן מילה כלשהי, לומר מייד אם היא שייכת לשפה או לא. למשל – אורקל לבעיית העצירה יכול, בהינתן זוג $M,x$ , להגיד מייד אם $M$ עוצרת על $x$ או שאינה עוצרת. זהו כמובן מושג תיאורטי לחלוטין; במציאות אפילו חישובים פשוטים דורשים זמן. עם זאת, התועלת שצומחת משימוש תיאורטי ביצור הזה היא עצומה, והדבר דומה לשימושיות הרבה של מושג המכונה האי-דטרמיניסטית, למרות שמכונה כזו אינה קיימת במציאות.

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

אלא מה? הוכחות רלטיביסטיות הן "עיוורות" לחיזוק שכזה. אם אנחנו מצליחים להוכיח באופן רלטיביסטי ששתי מחלקות $A,B$ שונות זו מזו, ואנו מחזקים את המכונות בשתי המחלקות באמצעות אותו אורקל, ההוכחה ממשיכה לעבוד באותו האופן; בכל פעם שסימולציה של מכונה $M$ מתוך $A$ תדרוש קריאה לאורקל, $U$ תוכל לבצע את הקריאה הזו כי גם ל- $B$ הוספנו גישה לאותו אורקל. באופן פורמלי זה אומר שאם הוכחנו רלטיביסטית ש- $A\ne B$ אז גם $A^{L}\ne B^{L}$ , כאשר $A^{L}$ אומר, כצפוי, "המחלקה $A$ כשמוסיפים למכונות בה גישה לאורקל לשפה $L$ ".

ומה שהראו באותו מאמר משנת 1975 היה שקיימות שתי שפות, $L_{1},L_{2}$ , כך ש- $\mbox{P}^{L_{1}}\ne\mbox{NP}^{L_{1}}$ , אבל $\mbox{P}^{L_{2}}=\mbox{NP}^{L_{2}}$ . זה מראה מייד שלא ניתן להוכיח לא ש- $\mbox{P}\ne\mbox{NP}$ בשיטות רלטביסטיות, וגם לא ש- $\mbox{P}=\mbox{NP}$ .

מהן השפות $L_{1},L_{2}$ המסתוריות הללו ואיך הולכת ההוכחה? מכיוון שהיא טכנית יחסית, אדחה אותה לפוסט נפרד.

תגים: משפטי היררכייה בסיבוכיות, לכסון, בעיית P=NP, בעיית העצירה
שייך לקטגוריות חישוביות, תורת הסיבוכיות | 6 תגובות »

אז מה זה עניין P=NP, בעצם?

15 באוגוסט, 2010

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

החשש שכעת מביעים חלק מהדוברים בעניין הוא שההוכחה הזו היא הסנונית הראשונה לבוא עידן שבו הוכחות-שגויות-שנראות-רציניות לכך ש-P שונה מ-NP יצוצו לעתים קרובות יחסית. ברור שמאמץ הירואי של בדיקת הוכחה – שבו חוקרים מהשורה הראשונה עוזבים את כל מה שהם עוסקים בו ושוברים את הראש על מאמר לא פשוט של 100 עמודים – לא יוכל לחזור על עצמו שוב ושוב ושוב. מכאן שצעקת ה"זאב" הראשונה הזו עלולה לגרום לבעיות לא פשוטות בהמשך, כשיצוצו הוכחות נוספות. כפי שהעיר מישהו (איני מוצא כעת את הציטוט המדויק), כל המהומה הזו היא מה שקורה כשמישהו כותב בראש המאמר שלו "P שונה מ-NP" במקום "גישה חדשה להתמודדות עם בעיית P נגד NP", שכנראה הייתה מובילה לבדיקה יותר איטית ושפויה של ההוכחה – אולי גם יותר מועילה.

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

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

טוב, נסחפתי.

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

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

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

ומאיפה האות P הגיעה בכלל? מהמילה Polynomial – פולינומי, שניתן לתיאור באמצעות פולינום. זהו שם טכני – "זמן ריצה יעיל" מזוהה עם "זמן ריצה שניתן לחסימה באמצעות פולינום" וממש לא נורא אם לא תבינו למה הכוונה כאן.

כעת ל-NP. בלבול מאוד נפוץ הוא לחשוב ש-NP פירושו "לא ב-P" (כלומר, שה-N מסמן "Not"). המשמעות האמיתית היא שוב טכנית – Nondeterminsitic Polynomial. מה קשור אי דטרמיניזם לכאן – זה כבר לדיון אחר, והסיבות הן בעיקר היסטוריות. המשמעות של NP, שהיא מה שחשוב כאן, היא זו: בעיות שקל לבדוק את פתרונן. וכאן מתאימה דוגמה – אם אומרים לי "הפירוק לגורמים של 35 הוא 5 ו-7", קל לי לבדוק זאת – אני כופל את 7 ו-5 ומקבל 35, כצפוי. עם זאת, לא ידוע כיום שום אלגוריתם יעיל לפירוק לגורמים של מספר – כך שזוהי בעיה שקל לבדוק את פתרונה, אך לא קל לפתור (ליתר דיוק – לא ידוע אם קל לפתור אותה). גם בעיית לוח הזמנים שדיברתי עליה למעלה היא כזו – אם נותנים לכם רשימה ארוכה של קורסים שיש לשבץ בכיתות ובשעות שלא יתנגשו, תחת אילוצים מסויימים, יכול להיות מאוד קשה למצוא מערכת שעות מוצלחת; אבל אם מישהו כבר מביא לכם כזו, קל לבדוק שהיא אכן מוצלחת. כפי שאפשר להבין מכך, NP היא מחלקת בעיות גדולה יותר מאשר P; כל מה שקל לפתור, קל גם לבדוק אם הוא פתיר (למי שהטענה הזו נשמעת קצת "חשודה", אל חשש – כשמביאים הגדרות מתמטיות מדוייקות למחלקות אלו, המשפט הזה מקבל משמעות יותר מדוייקת שנכונותה ברורה למדי).

השאלה האם P=NP או שמא P שונה מ-NP היא השאלה האם שתי הקבוצות הללו זהות, כלומר האם כל בעיה ב-NP היא גם ב-P, כלומר האם כל בעיה שמתאפיינת בכך שקל לבדוק פתרונות שלה, היא בעיה שקל לפתור?

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

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

כדי להמחיש עד כמה P=NP היא תוצאה חזקה באופן מופרז, הנה משחק מחשבתי – חשבו על בעיה כלשהי שהטרידה אתכם, ושקיים לה פתרון שאתם יכולים לשבת ולקרוא ולהבין – נניח, פתרון של מאה עמודים. אם P=NP, אז מחשב יכל לגלות את הפתרון הזה בעצמו, ללא מאמץ מיוחד. נשמע מוזר ומופרך? בוודאי! ראשית, כי אני מציג את הבעיה בצורה מופרכת; אבל שנית, כי התוצאה עצמה היא מופרכת בכוח שלה, ואיננה עד-כדי-כך שונה מהתיאור המטופש שנתתי כאן. הדוגמה על ההצפנה שתיארתי בהתחלה היא אפילו מציאותית למדי – אם יש תוכנית מחשב שבהינתן טקסט מוצפן יודעת לזהות שמשהו הוא הפיענוח הנכון שלו (בעיה שבפני עצמה אינה טריוויאלית בהקשרים מסויימים, אבל בחלקם – בפרט, בכל הנוגע להצפנת מפתח ציבורי – היא כן), אז קיימת תוכנה שבמאמץ לא שונה מהותית תוכל לפרוץ את ההצפנה ולגלות את הפיענוח הנכון. וזו רק דוגמה – התוצאה היא כללית וחזקה בהרבה.

סקוט אהרונסון פרסם מצגת שבה הוא מדבר על בעיית P=NP. הוא מנסה להמחיש עד כמה הוכחה ש-P=NP תהיה מפתיעה לקהילת מדעני המחשב בעזרת גרף שאני חושב שקולע בול לרעיון:

שימו לב לסקלה הלוגריתמית! אותה סקלה שבה משתמשים, למשל, במדידת רעידות אדמה. אם אינכם מכירים את התוצאות שמשמאל ל-P=NP, לא נורא – כולן תוצאות מפתיעות ומרתקות בתורת הסיבוכיות (למשל, האלגוריתם של שור הוא אלגוריתם יעיל לפירוק לגורמים במודל המחשב הקוונטי – אלגוריתם זה הקפיץ בצורה דרמטית את ההתעניינות בחישוב קוונטי). אם נמשיך בדוגמת רעידות האדמה – אם נפרש את הגרף כך שגם האלגוריתם של שור בסך הכל מתאים לרעידת אדמה קטנה ומסכנה, שבה בקושי שמים לב שאיזו כוס על השולחן בקומה 20 זזה טיפה לשנייה ואז מפסיקה – אז P=NP יתאים לרעידת אדמה שבה עיר מודרנית שלמה מתמוטטת וקורסת ונבלעת בלב האדמה. עד כדי כך יהיה מדובר על תוצאה מפתיעה.

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

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

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

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

תגים: מבוא למתמטיקה, שאלת P=NP, חדשות מתמטיות
שייך לקטגוריות בעיות מתמטיות מפורסמות, תורת הסיבוכיות | 14 תגובות »

דיון שאינו חסר תוחלת במשתנים מקריים

14 באוגוסט, 2010

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

שאלות מהסוג הזה מעבירות אותנו לשלב הבא בדיון שלנו על הסתברות, ונותנות לנו מוטיבציה להכנסה של מה שהוא אולי המושג המרכזי בהסתברות – המשתנה המקרי. הרעיון במשתנים מקריים הוא להוסיף לנו רמת אבסטרקציה "מעל" מרחב המדגם שמאפשרת לנו לשאול בנוחות שאלות יותר כלליות מאשר "מה הייתה תוצאת ההגרלה?". הדרך הפשוטה ביותר להסביר זאת היא באמצעות דוגמת הרולטה: בהימור רולטה מרחב המדגם שלנו הוא פשוט יחסית – יש 38 (או 37, תלוי ברולטה) תוצאות אפשריות, וכולן (תיאורטית) שוות הסתברות. לעומת זאת, הסכום שבו אני זוכה (או מפסיד) בסיבוב של הימור הוא כבר מספר שונה לגמרי, שמחושב בצורה מתוחכמת למדי מתוך תוצאת הרולטה (ותלוי, כמובן, גם באופן שבו אני מהמר). לא אכנס כאן לחוקי הזכייה המדוייקים כי אני בכלל לא יודע אותם; אבל לצורך פשטות אפשר להניח משהו מפגר כזה – שאם התקבל ברולטה מספר זוגי אני זוכה ב-5 ש"ח, ואם התקבל מספר אי זוגי אני מפסיד 5 ש"ח.

כעת אפשר למדל את הסיטואציה באופן הסתברותי על ידי שינוי של מרחב המדגם – במקום לדבר על מרחב המדגם של הרולטה נדבר על מרחב מדגם פשוט יותר, שאבריו הם הזכיות האפשריות שלי, ו- $5$ הוא בעל הסתברות חצי בו, וגם $-5$ הוא בעל הסתברות חצי בו, וחסל; אלא ששיטת עבודה שכזו, של שינוי מרחב המדגם, היא מסורבלת למדי באופן כללי, ובעייתית מאוד אם אנחנו רוצים לשאול שאלות מורכבות יותר – למשל, "בהינתן שבהטלת שתי קוביות סכום ערכי הקוביות הוא זוגי, מה ההסתברות שגם מכפלתן זוגית?". לכן משתלם להוסיף למשחק את המושג הפשוט של משתנה מקרי. פורמלית, משתנה מקרי הוא פשוט פונקציה ממרחב המדגם אל המספרים הממשיים (כמובן שאפשר גם יותר מכך אבל אני לא נכנס לזה פה), שמייצגת את ה"ערך" של כל תוצאה אפשרית. מסמנים משתנים מקריים לרוב באותיות לטיניות גדולות, ובפרט ב- $X$ . אפשר לחשוב על משתנה מקרי כאילו הוא מקבל ערכים באופן הבא: ראשית מבצעים את ההגרלה הבסיסית של מרחב המדגם, ולאחר מכן מחשבים את הפונקציה על תוצאת ההגרלה, וזהו ערכו של $X$ . לכן השאלה הבסיסית שאפשר לשאול על משתנה מקרי הוא "באיזו הסתברות אתה מקבל את הערך הזה והזה?". אנחנו נסמן $\mbox{P}\left(X=a\right)$ בתור ההסתברות ש- $X$ קיבל את הערך $a$ . זה כל הבסיס ההגדרתי שאנחנו צריכים כאן.

בואו ניקח דוגמה פשוטה. נניח שאנחנו מטילים שתי קוביות משחק רגילות, ומגדירים משתנה מקרי $X$ בתור סכומן. מה ההסתברויות לערכים שונים ומשונים ש- $X$ עשוי לקבל? ברור, למשל, ש- $\mbox{\mbox{P}}\left(X=1\right)=0$ כי הסכום הוא בין 2 ל-12 (ולכן בעצם $\mbox{P}\left(X=a\right)=0$ לכל $a$ שאינו מספר טבעי בין 2 ל-12). כדי לדעת את ההסתברויות לערכים אחרים, כדאי לחשוב קצת על מרחב המדגם שלנו – הוא כולל את כל הזוגות מהצורה $\left(a,b\right)$ כאשר $a,b$ בין 1 ל-6. סך הכל ישנם $6\cdot6=36$ זוגות אפשריים (עקרון הכפל הקומבינטורי). מכיוון שכל זוג הוא שווה-הסתברות, ההסתברות שלו הוא $\frac{1}{36}$ (עקרון ה"הסתברות במרחב סופי היא אחד חלקי קומבי") ולכן כדי לדעת מה ההסתברות לקבל $5$ , למשל, צריך לספור את כל הזוגות שנותנים בדיוק 5. זוגות אלו הם $\left(1,4\right),\left(2,3\right),\left(3,2\right)\left(4,1\right)$ ; שימו לב שיש חשיבות לסדר ו- $\left(1,4\right)$ ו- $\left(4,1\right)$ הם זוגות שונים (כי הראשון אומר "בהטלה הראשונה קיבלנו 1 ובשנייה 4" והשני אומר "בהטלה הראשונה קיבלנו 4 ובשנייה 1"). לכן ההסתברות לקבל 5 היא $\frac{4}{36}=\frac{1}{9}$ . את אותו חישוב אפשר לעשות לכל מספר; לא קשה לראות שההסתברות הגדולה ביותר היא לקבל 7, והיא $\frac{6}{36}=\frac{1}{6}$ ואת ההסתברות הנמוכה ביותר חולקים 2 ו-12, עם הסתברות של $\frac{1}{36}$ . בקיצור, המשתנה האקראי הזה מקבל ערכים בהסתברויות מאוד לא אחידות, למרות שמרחב המדגם המקורי היה מאוד אחיד. אני רוצה להכניס כאן לשימוש מילה חדשה – התפלגות; התפלגות של משתנה מקרי היא בסך הכל שם מקוצר ל"הערכים שהמשתנה המקרי עשוי לקבל וההסתברויות שבהם הוא עשוי לקבל אותן". אז במקרה הזה אני יכול לומר שהתפלגותו של $X$ היא מאוד לא אחידה.

הבה נעבור למשתנה מקרי מעניין יותר וחשוב הרבה יותר. נניח שאנחנו מטילים מטבע $n$ פעמים, אבל לא מדובר על מטבע הוגנת בהכרח – ההסתברות שהיא תיפול על "עץ" היא בדיוק $p$ , כאשר $0\le p\le1$ . מה ההסתברות שהמטבע תיפול בדיוק $k$ פעמים על עץ? כדי למדל את השאלה הזו אנו מגדירים משתנה מקרי $X$ ש"סופר" את מספר ההטלות שבהן התקבל עץ בהטלה, והשאלה שלנו היא מהו $\mbox{P}\left(X=k\right)$ לכל $0\le k\le n$ טבעי (ברור שלערכים אחרים ההסתברות היא 0 – מדוע?)

מפתה לומר עכשיו משהו בסגנון "ההסתברות ש- $X$ ייפול על עץ היא $p$ , אז מעקרון הכפל עולה שההסתברות שהוא ייפול על עץ בדיוק $k$ פעמים היא $p^{k}$ ". זו חשיבה בכיוון הנכון, אבל היא שגויה כי היא מתעלמת מגורם נוסף – $n$ , שהוזכר בתנאי השאלה ומאוד לא סביר שלא ישפיע כלל על הפתרון (זו דרך חשיבה נכונה לחיים באופן כללי – אם פתרתם תרגיל מבלי להשתמש בכל הנתונים, זה מצריך חשיבה נוספת – אם כי, כמובן, לפעמים באמת לא צריך את כל הנתונים והעובדה שהתוצאה אינה תלויה בנתון מסויים שעל פניו נראה הכרחי היא יפה). העניין הוא בכך שאנחנו רוצים שהמטבע יפול על עץ בדיוק $k$ פעמים; ב- $n-k$ ההטלות הנותרות אנחנו רוצים לקבל פלי. ההסתברות לקבל פלי היא $1-p$ (כי מקבלים או עץ או פלי, וסכום ההסתברויות לקבלת שניהם יחד צריך להיות 1), ולכן ההסתברות לקבל $k$ פעמים עץ וביתר הפעמים פלי היא $p^{k}\left(1-p\right)^{n-k}$ . כדי לפשט טיפה את הסימון נהוג להגדיר $q=1-p$ ואז אפשר לכתוב את ההסתברות הזו בתור $p^{k}q^{n-k}$ .

אבל רגע, גם זה לא נכון! כי שוב, התעלמנו כאן ממשהו. הדרך הטובה לראות זאת היא לבדוק מקרים פרטיים קטנים. נניח ש- $n=2$ ו- $k=1$ והמטבע הוגן, כלומר $p=\frac{1}{2}$ . אז הצבה בנוסחה נותנת לנו $\left(\frac{1}{2}\right)^{1}\cdot\left(\frac{1}{2}\right)^{1}=\frac{1}{4}$ , כלומר שההסתברות לקבל עץ באחת משתי הטלות היא רבע. אבל בואו נכתוב רגע את מרחב המדגם באופן מפורש, כש-1 הוא תוצאה של עץ ו-0 היא תוצאה של פלי: $\left\{ \left(0,0\right),\left(1,0\right),\left(0,1\right),\left(1,1\right)\right\}$ . קל לראות שבדיוק בשתיים מארבע התוצאות מקבלים פעם אחת עץ, כלומר ההסתברות צריכה להיות חצי. מה השתבש?

מה שקרה הוא שהתעלמנו מכך שעץ יכול להתקבל פעם אחת בכמה אופנים שונים. במקרה הפשוט שלנו, אפשר לקבל פעם אחת עץ בהטלה הראשונה (ואז בשניה יהיה פלי), או שאפשר לקבל עץ פעם אחת בהטלה השניה (ואז בראשונה יהיה פלי). זה לא בא לידי ביטוי בספירה שלנו. באופן כללי, התשובה $p^{k}q^{n-k}$ איננה התשובה הנכונה לשאלה "מה ההסתברות שעץ יתקבל בדיוק $k$ פעמים" אלא לשאלה "מה ההסתברות שעץ יתקבל בדיוק ב- $k$ המקומות הספציפיים הבאים…". למשל, מה ההסתברות שעץ יתקבל בדיוק ב- $k$ ההטלות הראשונות, או ב- $k$ ההטלות האחרונות, וכדומה. לכל בחירה אפשרית של $k$ מקומות שבהם יתקבל עץ, ההסתברות שדווקא הסיטואציה הזו תתקיים היא $p^{k}q^{n-k}$ ; אבל יש הרבה בחירות אפשריות כאלו. כמה יש? ובכן, כשדיברנו על קומבינטוריקה כיסינו בדיוק את השאלה הזו – יש ${n \choose k}$ בחירות אפשריות שכאלו, ולכן $\mbox{P}\left(X=k\right)={n \choose k}p^{k}q^{n-k}$ . נראה מוכר? אכן, ${n \choose k}p^{k}q^{n-k}$ היה בדיוק האיבר הכללי בנוסחת הבינום של ניוטון; ולכן ההתפלגות של $X$ שלנו מכונה "התפלגות בינומית". מכיוון שההתפלגות הבינומית תלויה בשני ערכים – מספר החזרות $n$ וההסתברות להצלחה בכל חזרה $p$ , נהוג לכתוב $X\sim\mbox{Bin}\left(n,p\right)$ (קרי: " $X$ מתפלג בינומית עם פרמטרים $n,p$ ") כדי לתאר באופן מקוצר את ההתפלגות הזו.

בדיקת השפיות שיש לעשות לאחר חישוב התפלגות של משתנה מקרי כלשהי היא לסכום את הסתברות כל הערכים ש- $X$ יכול לקבל ולוודא שקיבלנו 1. במקרה שלנו, פירוש הדבר הוא לבדוק שהסכום $\sum_{k=0}^{n}{n \choose k}p^{k}q^{n-k}$ הוא 1. כאן נחלץ הבינום של ניוטון לעזרתנו – הסכום הזה שווה, על פי הבינום של ניוטון, ל- $\left(p+q\right)^{n}$ ; אבל $p+q=1$ ולכן הסכום אכן שווה ל-1, כנדרש. שימו לב שכאן אנחנו משתמשים בנוסחת הבינום בכיוון שהוא לכאורה ההפוך – במקום "לפתוח" את הסוגריים אנחנו דווקא מצמצמים סכום "אל תוך" הסוגריים. זה שימוש שיותר נדיר לראות כשאתה תיכוניסט ופותר תרגילים טכניים, אבל הוא כנראה יותר נפוץ בעולם המתמטי האמיתי.

בואו נעבור עכשיו לשאלה של תחילת הפוסט – מהו "הערך הממוצע" שמקבל משתנה מקרי. הערך הזה מכונה תוחלת, ונהוג לסמן אותו ב- $\mbox{E}\left[X\right]$ (E מהמילה Expectation). כדי לראות איך מחשבים אותו, בואו ונתבונן בדוגמה פשוטה – שוב הטלת מטבע עם הסתברות $p$ לקבלת עץ. נניח שכשיוצא עץ אנחנו מרוויחים 2 ש"ח, וכשיוצא פלי אנחנו מפסידים 3 ש"ח – עבור איזו הסתברות $p$ נוכל בממוצע להרוויח? די ברור ש- $p$ צריך להיות גדול מחצי כי המשחק אינו הוגן, אבל כמה?

בואו נניח שאנחנו משחקים $n$ משחקים, ומתוכם ב- $a$ משחקים קיבלנו עץ, וב- $b$ משחקים קיבלנו פלי. אז הרווח הממוצע שלנו הוא $\frac{2a-3b}{n}$ – זהו בעצם ממוצע משוקלל שבו המשקולת של התוצאה $2$ היא מספר הפעמים הצפוי שהיא תצוץ בו, וכך עבור התוצאה $-3$ . את הממוצע המשוקלל הזה אפשר לכתוב גם כ- $2\frac{a}{n}-3\frac{b}{n}$ . ככל ש- $n$ גדול יותר כך אנו מצפים שהערכים $\frac{a}{n}$ ו- $\frac{b}{n}$ ילכו ויתייצבו – אנו מצפים ש- $\frac{a}{n}$ יישאף ל- $p$ (ולכן ש- $\frac{b}{n}$ יישאף ל- $q$ ). זהו כמובן נפנוף ידיים, אבל חשוב לזכור שאי אפשר להוכיח מתמטית את הטענה הזו, שהיא בסופו של דבר טענה אמפירית, ואפילו הגדרתית; הרי איך אנחנו מפרשים את "ההסתברות שהאירוע יקרה היא $p$ " אם לא בתור "כשנחזור על אותו ניסוי מספר רב של פעמים הפרופורציה של הפעמים שבהן נקבל את התוצאה הזו תשאף ל- $p$ "? (ובכן, כן, יש דרכים שונות לגשת לכך, אבל זה כבר עניין לפוסט נפרד).

אם כן, הרווח הממוצע שלנו שואף ל- $p\cdot2+q\cdot\left(-3\right)$ . ושוב, הדרך הנכונה לחשוב על כך היא כעל שקלול של הערכים האפשריים ש- $X$ יכול לקבל, כשהמשקולת של כל ערך היא ההסתברות שנקבל אותו. אם נציב $q=1-p$ נקבל $\mbox{E}\left[X\right]=2p-3\left(1-p\right)=5p-3$ , ולכן כאשר $p=\frac{3}{5}$ התוחלת היא אפס (כלומר, אנחנו לא מצפים לא להרוויח ולא להפסיד מהמשחק בטווח הארוך) וכמובן שעבור ערכי $p$ גדולים יותר היא תהיה חיובית.

באופן יותר כללי ופורמלי התוחלת מוגדרת כך: $\mbox{E}\left[X\right]=\sum a\cdot\mbox{P}\left[X=a\right]$ , כשהסכום נלקח על פני כל הערכים $a$ שהמשתנה $X$ בכלל יכול לקבל. אתם עשויים לשאול מה יקרה אם $X$ יכול לקבל אינסוף ערכים שונים; במקרה זה אכן מקבלים סכום אינסופי וצריך לטפל בו בכלים המתאימים לסכומים אינסופיים – חומר שחורג ממה שנלמד בתיכון, אך הוא סטנדרטי למדי במתמטיקה אוניברסיטאית.

לעת עתה, הבה ונבצע חישוב שהוא סופי, אך גם כן אינו פשוט לגמרי – נניח כי $X\sim\mbox{Bin}\left(n,p\right)$ , מהי $\mbox{E}\left[X\right]$ ? הבה ונבצע את החישוב באופן ישיר, על פי ההגדרה: $\mbox{E}\left[X\right]=\sum_{k=0}^{n}k\cdot{n \choose k}p^{k}q^{n-k}$ . אוי ווי. מבט אחד בסכום ובא לבכות. איך בכל זאת מטפלים בסכומים כאלו? ובכן, יש תעלולים שמשתמשים בחשבון דיפרנציאלי בסיסי ומאפשרים לחשב אותו במדוייק, אך זה דורש פוסט משל עצמו ואני מעדיף לא להיכנס לכך כעת. במקום זאת אציג גישה שונה לגמרי לחישוב התוחלת, שתהפוך את פתרון השאלה הזו לטריוויאלי, ובתקווה תתחיל להמחיש עד כמה הדיבורים על משתנים מקריים מועילים לנו.

בואו נדבר לרגע על בעיה שלכאורה בלתי קשורה בעליל לבעיה שלנו – נניח שיש לנו מרחב הסתברות ומעליו אנו מגדירים שני משתנים מקריים שונים $X,Y$ (למשל – $X$ הוא סכום הערכים בהטלת שתי קוביות ו- $Y$ הוא מכפלתם). כעת אנו מסוגלים להגדיר באמצעותם משתנים מקריים נוספים, למשל $Z=X+Y$ . האם ניתן לתאר את $\mbox{E}\left[Z\right]$ באופן פשוט באמצעות $\mbox{E}\left[X\right]$ ו- $\mbox{E}\left[Y\right]$ ? למשל, האם אפשר לקוות למשוואה יפה כמו $\mbox{E}\left[Z\right]=\mbox{E}\left[X\right]+\mbox{E}\left[Y\right]$ ? התשובה חיובית. למעשה, למרות שזה אולי לא נראה כך, זו תשובה מפתיעה למדי למי שכבר השתפשף קצת, שכן היא נכונה בלי קשר לשאלה האם יש תלות בין $X,Y$ או אין. איכשהו אנחנו מצליחים לחשב את תוחלת $Z$ על ידי הסתכלות על $X$ ו- $Y$ בנפרד, למרות שכל ערך ש- $Z$ מקבל תלוי בתוצאה של שניהם יחד (עם זאת, לעתים התלות כן חשובה – למשל, $\mbox{E}\left[XY\right]=\mbox{E}\left[X\right]\mbox{E}\left[Y\right]$ לא מתקיים תמיד, אבל כן מתקיים בודאות אם הם בלתי תלויים). ההוכחה של הטענה הזו אינה כה קשה אך היא דורשת הכנסת עוד מושג אחד לתמונה (התפלגות משותפת של משתנים מקריים) ולא אכנס לכך כעת.

כעת הבה ונסתכל על המשתנה הבינומי באופן קצת שונה. נגדיר משתנים $X_{1},X_{2},\dots,X_{n}$ כך ש- $X_{k}$ הוא המשתנה שמקבל 1 אם בהטלת המטבע ה- $k$ -ית התקבל עץ, ו-0 אם התקבל פלי. למשתנה כזה, שמקבל או 0 או 1, קוראים "אינדיקטור", ואחד היתרונות שבו הוא שחישוב התוחלת שלו טריוויאלי: על פי הגדרה, $\mbox{E}\left[X_{i}\right]=p\cdot1+q\cdot0=p$ , כלומר התוחלת של אינדיקטור שווה להסתברות שהוא יקבל 1.

כעת, $X=\sum_{k=0}^{n}X_{k}$ – לכל סדרת הטלות במרחב המדגם, מספר ההטלות שבהן התקבל עץ באותה סדרה שווה למספר האינדיקטורים שקיבלו 1 עבור סדרה זו. על פי נוסחת התוחלת שלמעלה (שניתנה עבור שני משתנים אבל נכונה באותה המידה גם עבור $n$ או כל סכום סופי אחר של משתנים), החישוב הוא כעת טריוויאלי:

$\mbox{E}\left[X\right]=\mbox{E}\left[\sum_{k=0}^{n}X_{k}\right]=\sum_{k=0}^{n}\mbox{E}\left[X_{k}\right]=\sum_{k=0}^{n}p=np$

וזוהי אכן התוחלת של משתנה שמתפלג בינומית עם פרמטרים $n,p$ – וגם אינטואיטיבית תוצאה זו די ברורה (אם למשל $p=\frac{1}{2}$ , אנחנו מצפים שבערך בחצי מההטלות נקבל עץ, כלומר ב- $n\cdot\frac{1}{2}$ ). עם זאת, ברור שהחישוב שנתתי כעת קל מהחישוב הטכני שהיינו צריכים לבצע אם היינו משתמשים ישירות בהגדרה. כמו שאוהבים לומר, מתמטיקאים הם עצלנים, ולכן התוצאות התיאורטיות שהם מוכיחים נועדות (לפעמים…) לעשות את החישובים המעצבנים לקלים יותר.

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

תגים: משתנים מקריים, מתמטיקה תיכונית, תורת ההסתברות, תוחלת, התפלגות בינומית
שייך לקטגוריות הסתברות | 10 תגובות »

הוכחה ש-P שונה מ-NP?

10 באוגוסט, 2010

למרות שאני לא אוהב לכתוב פוסטים "חדשותיים", נראה לי שאין מנוס מכך הפעם. בימים האחרונים נוצר באזז עצום סביב הוכחה לכך ש-P שונה מ-NP (מה הבעיה הזו בכלל? על כך דיברתי כאן), וגם אני לא יכול להתעלם ממנו. למי שמעוניין לקרוא טיוטה של ההוכחה (שדלפה לרשת ואיננה הגרסה הרשמית של כותב ההוכחה אלא משהו שהוא שלח באופן פרטי לעמיתים), הנה היא. למי שמעוניין לקרוא מה בלוגים טובים ממני אומרים – הנה לינק אחד, ועוד אחד. ולמי שרוצה לשמוע את דעתי, הנה היא בקצרה:

ראשית, לא קראתי את ההוכחה אלא רק רפרפתי עליה. היא לא קצרה במיוחד (אם כי גם לא ארוכה עד כדי כך) וכבר מהצצה חטופה ברור לי שיידרש לי זמן מה כדי להבין מה קורה שם, ואני מעדיף לחכות עד שגדולים ממני יפסקו בעניין. מה שכן אפשר לומר על ההוכחה הזו – הן מהמבט שנתתי בה, אבל בעיקר ממה שאחרים כבר אמרו – היא לא נראית מופרכת. חשוב להבין שהוכחות לכך ש-P שונה מ-NP, או שווה לו, או שהבעיה בכלל לא כריעה, צצות כל הזמן ברשת ולרוב מקורן בטרחנים שאין להם מושג על מה הם מדברים. הנה דוגמה להוכחה גרועה במיוחד לכך שהבעיה היא אי כריעה (תקציר: "משפט גדל מראה שלא ניתן לדעת הכל, אז בטח גם את P=NP אי אפשר לדעת"). ההוכחה הנוכחית היא יוצאת דופן בכך שהיא חד משמעית איננה הוכחה של טרחן ולא ניתן לפסול אותה על הסף כשטויות. זו הוכחה של חוקר רציני עם רקורד קיים, שכבר התעסק בוריאציות על הבעיה ואמר עליהן דברים לא טריוויאליים, וגם חוקרים נודעים במדעי המחשב (ציטטו בפרט את סטיבן קוק, ההוא ממשפט קוק-לוין למי שמכיר) דיברו בחיוב על ההוכחה. מכאן שגם אם ההוכחה אינה נכונה, היא ללא ספק משהו שיש להתייחס אליו ברצינות.

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

ונניח שההוכחה נכונה, מה הלאה? ובכן, שום דבר לא קורס ושום דבר מהותי לא משתנה, בעצם. הוכחה ש-P=NP הייתה סנסציה מדהימה; היא הייתה גורמת לקריסת תחומים שלמים במדעי המחשב; היא הייתה, למשל, מוחקת לחלוטין את תחום התיאוריה של הקריפטוגרפיה; ובהתאם לאופן שבו ההוכחה הייתה מתבצעת (למשל, על ידי מתן אלגוריתם יעיל מפורש לבעיה קיימת – ויעיל באופן מציאותי ולא רק תיאורטי), היו עשויות להיות לה גם השלכות מעשיות רבות. אבל הוכחה ש-P שונה מ-NP היא בדיוק מה שמדעני המחשב מצפים לו כבר שנים רבות, וכמעט כולם פועלים תחת ההנחה הזו. אין שום דבר מפתיע בכך שהטענה נכונה, אלא רק בכך שהצליחו למצוא לה הוכחה. מה שזה אומר הוא שלא סביר שההוכחה הזו תשנה מהותית את פני מדעי המחשב, אבל היא כן תסיר את הזרקור מהכוכב המרכזי של הבעיות הפתוחות בענף זה – כל ספר על התיאוריה של מדעי המחשב ייאלץ להוציא מהדורה חדשה.

חשוב גם להבין שההוכחה הזו היא של תוצאה חלשה. להראות ש-P שונה מ-NP זה רק המינימום שבמינימום שבין השאלות הפתוחות המציקות לנו – האם NP שונה מ-coNP? האם קיימת פונקציה חד כיוונית? האם קיים מחולל מספרים פסאודו-אקראיים? האם ההיררכייה הפולינומית קורסת? אלו כמה דוגמאות לשאלות מהותיות שנותרות ללא מענה (ואם היה מתברר ש-P=NP היה ניתן להן מענה) – מי שלא מכיר את המושגים, לא נורא, אם כי אני מקווה להרחיב בעניינים הללו בבלוג (על חלקם כבר סיפרתי משהו). אם כן, ההוכחה הזו לא מביאה לסופם את מדעי המחשב התיאורטיים – אפילו לא נכון לומר שהבעיה הגדולה נענתה וכעת נותרו רק בעיות "קטנות"; אם כבר, ההוכחה הזו מבשרת את תחילתו של עידן חדש שבו ההתמודדות תהיה עם בעיות פתוחות גדולות אף יותר מהנוכחית, מתוך תקווה שאכן ניתן סוף סוף להתמודד איתן.

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

תגים: שאלת P=NP, חדשות מתמטיות
שייך לקטגוריות בעיות מתמטיות מפורסמות, תורת הסיבוכיות | 17 תגובות »

בהינתן שאנחנו יודעים הסתברות בסיסית, כמה קל להבין הסתברות מותנית?

5 באוגוסט, 2010

בפוסט הקודם התחלתי לדבר על הסתברות בסיסית והצגתי כמה רעיונות בסיסיים. אמרתי שאנחנו ממדלים סיטואציה הסתברותית עם מרחב הסתברות שכולל קבוצה $X$ (מרחב המדגם) של כל התוצאות האפשריות של הסיטואציה ההסתברותית, כך שלכל $a\in X$ (לכל תוצאה $a$ אפשרית ששייכת לקבוצה $X$ ) מותאם גם מספר $P\left(a\right)$ בין 0 ל-1 שאומר מה ההסתברות של התוצאה הזו, וסכום ההסתברויות של כולם הוא 1. כמו כן אמרתי שמה שמעניין אותנו בדרך כלל הוא מאורעות, שהם תת-קבוצות של $X$ (מסמנים זאת $A\subseteq X$ ) ומהווים אוסף של כמה תוצאות אפשריות בעלות משמעות "דומה". למשל, בהטלת קוביה התוצאות הבסיסיות הן $1,2,3,4,5,6$ ואילו מאורעות אפשריים הם "הקוביה נפלה על מספר זוגי", "הקוביה נפלה על מספר גדול מ-4", "הקוביה נפלה על 2, או על 3, או על 5"וכדומה. ההסתברות של מאורע, שסימנתי $P\left(A\right)$ , הייתה פשוט סכום ההסתברויות של איבריו.

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

האינטואיציה היא בערך כך: אם נפלתי על מספר זוגית אז ההסתברות שנפלתי על 1,3,5 היא אפס – הם יצאו מהמשחק. כלומר, נפלתי או על 2, או על 4, או על 6. מכיוון שקודם ההסתברות שלי ליפול על כל אחד מהם הייתה זהה, והמידע החדש לא מסייע לי להבדיל ביניהם, גם עכשיו ההסתברות שלי ליפול על כל אחד מהם היא זהה, ומכיוון שסכומם צריך להיות 1, ההסתברות של כל אחד מהם היא $\frac{1}{3}$ . לכן ההסתברות של 2 היא $\frac{1}{3}$ וזו התשובה. אכן, אם תעשו סימולציה ממוחשבת של הטלת קובייה ותבדקו באיזה אחוז מהמקרים מקבלים 2 אם בהטלת הקוביה התקבל מספר זוגי (ואחרת פשוט מתעלמים מהטלת הקוביה הזו), תקבלו בערך $\frac{1}{3}$ . אז איך אפשר להצדיק את הקסם הזה פורמלית ולטפל בסיטואציות יותר מורכבות?

הרעיון הבסיסי של הסתברות מותנית הוא שינוי מרחב ההסתברות שלנו. אם יש לנו מרחב מדגם $X$ ומאורע $B$ ואומרים לנו שהמאורע $B$ התרחש, זה אומר שאפשר לשכוח מהקבוצה $X$ המקורית ולהגדיר מרחב הסתברות חדש שבו מרחב המדגם הוא $B$ . יש "לתקן" את ההסתברויות בהתאם, כדי שסכום ההסתברויות של התוצאות שנמצאות ב- $B$ יהיה 1; לפעולה הזו קוראים נורמליזציה והיא נפוצה למדי במתמטיקה. מה שעושים הוא פשוט לחשב את סכום כל התוצאות שב- $B$ (שהוא פשוט $P\left(B\right)$ ) ואז לחלק את ההסתברות של כל איבר ב- $B$ במספר זה. כעת ברור שסכום כל ההסתברויות החדשות של אברי $B$ יסתכם ל-1. אם נסמן ב- $P^{\prime}$ את ההסתברות החדשה שנתנו לכל איבר של $B$ אז $P^{\prime}\left(a\right)=\frac{P\left(a\right)}{P\left(B\right)}$ לכל $a\in B$ , ועל כן

$\sum_{a\in B}P^{\prime}\left(a\right)=\sum_{a\in B}\frac{P\left(a\right)}{P\left(B\right)}=\frac{1}{P\left(B\right)}\sum_{a\in B}P\left(a\right)=\frac{P\left(B\right)}{P\left(B\right)}=1$

כך שפורמלית השגנו את המטרה שלנו.

מהדבר הזה נובעת נוסחה פשוטה יחסית: אם $A,B\subseteq X$ הם מאורעות כלשהם במרחב המדגם המקורי, ואנחנו רוצים לדעת מה ההסתברות ש- $A$ יתקיים אם ידוע ש- $B$ התקיים, אז מפתה לכתוב שהסתברות זו היא $\frac{P\left(A\right)}{P\left(B\right)}$ . לרוע המזל, זה לא נכון כי ייתכן שחלק מאברי $A$ בכלל לא נמצאים ב- $B$ . אם $A=X$ עצמו, אז נקבל את התוצאה הלא הגיונית שההסתברות שהקוביה תיפול על משהו (שהיא כמובן 1) הופכת פתאום ל- $\frac{1}{3}$ כשאנחנו יודעים שהתקבל מספר זוגי. לכן צריך לתקן קצת את הנוסחה – מה שבמונה צריך להתייחס רק לאיברים של $A$ שהם גם איברים של $B$ . מסמנים את קבוצת האיברים המשותפים של $A,B$ כ- $A\cap B$ (החיתוך של $A$ ו- $B$ ), ולכן הנוסחה הנכונה היא $\frac{P\left(A\cap B\right)}{P\left(B\right)}$ . לצורך פשטות נהוג לסמן זאת כ- $P\left(A|B\right)=\frac{P\left(A\cap B\right)}{P\left(B\right)}$ (כלומר, $P\left(A|B\right)$ הוא ההסתברות של " $A$ בהינתן $B$ "). אגב, שימו לב שאם $P\left(B\right)=0$ הנוסחה אינה חוקית כי קיבלתי חלוקה באפס; ואכן, אין ממש הגיון בלשאול מה ההסתברות ש- $A$ יתרחש אם נתון שהתרחש $B$ למרות של- $B$ אין שום סיכוי לקרות.

דרך אחרת ונחמדה לכתוב את הנוסחה הזו היא $P\left(B\right)\cdot P\left(A|B\right)=P\left(A\cap B\right)$ . כלומר, ההסתברות שגם $A$ וגם $B$ יתרחשו ניתנת לחישוב כתהליך דו שלבי – קודם מחשבים מה ההסתברות ש- $B$ יתקיים, ואז מחשבים מה ההסתברות ש- $A$ יתקיים בהינתן ש- $B$ מתקיים. לעתים קרובות חישוב מותנה שכזה קל לביצוע באופן ישיר ואז אופן החישוב הזה חוסך לנו עבודה. עוד דבר שנראה בבירור בנוסחה הזו הוא הסימטריה שלה – באותו האופן בדיוק אני יכול לכתוב $P\left(A\right)\cdot P\left(B|A\right)=P\left(A\cap B\right)$ , ואז לקבל את השוויון $P\left(B\right)\cdot P\left(A|B\right)=P\left(A\right)\cdot P\left(B|A\right)$ . על ידי העברת אגפים קלה מקבלים את הנוסחה הבאה, שהיא חשובה ביותר:

$P\left(A|B\right)=\frac{P\left(A\right)}{P\left(B\right)}P\left(B|A\right)$

הנוסחה הזו מכונה "נוסחת בייס", והיא מאפשרת לנו לחשב הסתברות מותנית שנדמית "הפוכה" בעזרת הכרה של ההסתברות של שני המאורעות בנפרד ושל ההסתברות המותנית "ההגיונית". כאן המקום לזרוק לפח את דוגמת הקוביה ולעבור לתאר סיטואציות יותר מעניינות שבהן ה"מוזרות" שבנוסחת בייס בולטת הרבה יותר. עיקר החוכמה היא בבחירה של מאורעות $A,B$ כך שכלל לא נראה ש- $B$ גורר את $A$ בצורה כלשהי, אלא ההפך. יוסי לוי השתמש בבלוג שלו בדוגמה של בדיקת סמים לספורטאי; אצלו $A$ היה "השחקן משתמש בסמים" ו- $B$ היה "בבדיקה התגלו סמים". כאן נראה ש- $A$ הוא זה שמשפיע על $B$ ולא להפך – אם יודעים משהו על איכות בדיקת הסמים אפשר לחשוב באופן ישיר מה ההסתברות שהיא תצליח בהינתן שהשחקן באמת משתמש בסמים – אך איך אפשר להסיק מכך את ההפך? בניסוח קצת חרטטני – אם הסתברות מותנית נראית לנו במבט ראשון ככלי שבו אנחנו מסיקים מידע לגבי ההשפעה של העבר על העתיד ("השחקן השתמש בסמים וכתוצאה מכך הוא נכשל בבדיקה"), נוסחת בייס מראה לנו שגם ניתן להסיק מהעתיד על העבר.

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

הסטודנטים הזועמים רוצים לדעת מי דפק להם את הפקטור. ליתר דיוק, האם הוא עתודאי או לא (העתודאים הם דופקי פקטורים ידועים לשמצה ובשל כך – בין היתר – נחשבים למעמד התחתון בהיררכיית המזון האוניברסיטאית). איזה חישוב עליהם לעשות? ובכן, $A$ יהיה המאורע "הסטודנט הוא עתודאי" ו- $B$ יהיה המאורע "הסטודנט קיבל 103 במבחן הבלתי אפשרי", ואנחנו רוצים לדעת מהו $P\left(A|B\right)$ . שימו לב שכדי לדעת זאת אנחנו צריכים לדעת שלושה פרטים: $P\left(A\right)$ , שהוא ההסתברות לכך שסטודנט יהיה עתודאי; $P\left(B\right)$ שהוא ההסתברות שסטודנט כלשהו יקבל 103 במבחן הבלתי אפשרי; ו- $P\left(B|A\right)$ , שהיא ההסתברות שעתודאי יקבל 103 במבחן הבלתי אפשרי. מכיוון שלא מדובר בבעיה מתמטית מופשטת ברור שאין לנו דרך אמיתית לקבל את הנתונים הללו, אבל אפשר להעריך אותם סטטיסטית.

ובכן, נניח שמספר הסטודנטים הכולל בטכניון הוא 10,000 ומתוכם יש 50 עתודאים. אז מה ההסתברות שסטודנט אקראי יהיה עתודאי? $P\left(A\right)=\frac{50}{10000}=\frac{1}{200}$ .

הנתון לגבי ההסתברות לקבל 103 במבחן הבלתי אפשרי הוא הרבה יותר קשה לחילוץ, שהרי המבחן הזה ניתן רק פעם אחת, ועל קבוצה יחסית קטנה של סטודנטים. אבל כאמור, אנחנו לא רציניים כאן לגמרי. אז בואו נסתכל על מה שקורה "בדרך כלל" במבחנים קשים ונעשה מיצוע לאורך זמן. נניח שהתוצאה מראה לנו שבדרך כלל סטודנט אחד ממאה מצליח לקבל ציון שכזה – כלומר, ההסתברות לסטודנט גנרי כלשהו לקבל 103 במבחן הבלתי אפשרי היא $P\left(B\right)=\frac{1}{100}$ .

ועכשיו, מה ההסתברות של עתודאי לקבל 103 במבחן הבלתי אפשרי? מכיוון שעתודאים הם צורת חיים חדשה ומתקדמת אפשר להניח שההסתברות שלהם להצליח היא לא פחות מ- $P\left(B|A\right)=\frac{99}{100}$ . עכשיו בואו ונדחוף את כל הנתונים לנוסחה ונראה מה נקבל: $P\left(A|B\right)=\frac{P\left(A\right)}{P\left(B\right)}P\left(B|A\right)=\frac{1/200}{1/100}\frac{99}{100}=\frac{100}{200}\frac{99}{100}=\frac{99}{200}$ . כלומר, קיבלנו הסתברות של כמעט חמישים אחוז. מצד אחד, זה הרבה. מצד שני, אולי זה לא הרבה כפי שציפינו. תחשבו על הפער האדיר הזה: אם ניקח סטודנט מהרחוב, ההסתברות שלו לקבל 103 במבחן היא אפסית – $\frac{1}{100}$ . מצד שני, לעתודאי ההבטחה כמעט מוצלחת – $\frac{99}{100}$ . ועם זאת, ההסתברות שמי שקלקל את המבחן היה סתם סטודנט ולא עתודאי היא הגדולה יותר. למה זה קרה? בגלל הנתון (הלא ריאליסטי, המהונדס לצרכי השאלה – אבל כך גם ה- $\frac{99}{100}$ של העתודאי להצליח במבחן) שרק אחד מכל מאתיים סטודנטים הוא עתודאי.

במאמר ב-Ynet מראה ישראל בנימיני עד כמה התופעה הזו יכולה להיות מבלבלת, בהקשר העגום של בדיקת מחלות. אציג את מה שהמאמר הציג בצורה קצת מפושטת ובנוסף אשתיל פנימה טעות מזעזעת (שאתייחס אליה אחר כך) ונראה אם תגלו מהי. ובכן, נניח שיש לנו בדיקה מעולה לגילוי מחלה מסויימת, שעל 100 אחוז מהאנשים החולים מחזירה תוצאה חיובית, ורק על אחוז אחד מהאנשים הבריאים מחזירה תוצאה חיובית. כמו כן ידוע לנו ששיעור המחלה באוכלוסיה הוא אחד מאלף אנשים. אם נסמן ב- $A$ את "האדם חולה" וב- $B$ את "תוצאת הבדיקה חיובית", הרי ש- $P\left(B|A\right)=1$ , $P\left(A\right)=\frac{1}{1000}$ ו- $P\left(B\right)=\frac{1}{100}$ . נוסחת בייס נותנת לנו כאן מייד ש- $P\left(A|B\right)=\frac{1}{10}$ , תוצאה שנראית מפתיעה ביותר ממבט ראשון – למרות שהבדיקה כל כך טובה ומדוייקת (לכאורה…), רק עשרה אחוז מהאנשים שמקבלים תשובה חיובית אכן חולים במחלה! זו אחת מהנקודות שחשוב לזכור גם בחיי היום יום שלנו: גם אם מבחן נראה לנו טוב במדד של "ההסתברות שהוא טועה היא נמוכה" זה עדיין לא אומר שהוא טוב גם במובן שחשוב לנו באמת, של "כשמפעילים את המבחן שוב ושוב, כמעט ולא יהיו טעויות". כך הדבר בבדיקת מחלות, או בבדיקה האם הודעות הן דואר זבל, או בבדיקה האם מוצר שיצא מקו ייצור הוא פגום, וכדומה. נוסחת בייס היא השיעור הראשון בסקפטיות שיש ללמוד כשבאים להתייחס לתוצאות סטטיסטיות.

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

ובכן, נסמן ב- $A$ את "המספר ראשוני" וב- $B$ את "המספר עבר בהצלחה את המבחן". ברור כי $P\left(B|A\right)=1$ . נניח שאנחנו מגרילים מספרים בתחום שבין $1$ ו- $n$ , אז משפט המספרים הראשוניים מראה כי ההסתברות שלנו לפגוע בראשוני היא $\frac{1}{\ln n}$ . במילים אחרות, $P\left(A\right)=\frac{1}{\ln n}$ . הנעלם בכל הסיפור הזה הוא ההסתברות של מילר-רבין לטעות, ואותה אנחנו מסמנים ב- $x$ . אם כן, $P\left(B\right)=x$ ו… רגע, רגע, רגע. אי אפשר לעשות את אותה הטעות פעמיים, חייבים כבר להתייחס אליה במפורש. קודם התחמקתי ממנה כדי לא לסבך את הפשטות של ההצגה עם איזו מהומה טכנית, אבל עכשיו אין מנוס מלהוציא את הפרטים המלוכלכים החוצה. $P\left(B\right)$ אינו יכול להיות שווה ל- $x$ , כי $x$ מייצג את ההסתברות שהמבחן יגיד "כן" רק על קלטים שהם לא ראשוניים, בעוד ש- $P\left(B\right)$ מייצג את ההסתברות שהמבחן יגיד כן על קלט כלשהו! אז מה עושים? אין מנוס מלחשב את $P\left(B\right)$ בצורה קצת יותר רצינית, פשוט על ידי חלוקה למקרים: אם המספר הוא ראשוני, אז ההסתברות שהמבחן יגיד "כן" היא 1; ואם המספר הוא פריק, אז ההסתברות שהמבחן יגיד "כן"היא $x$ . יש לנו כאן סכום של שתי הסתברויות מותנות שונות. אולי תזכרו שבפוסט הקודם אמרתי שאם $A$ הוא מאורע אז מסמנים ב- $\overline{A}$ את המאורע ה"משלים" לו וההסתברות שלו היא $P\left(\overline{A}\right)=1-P\left(A\right)$ ? זה בדיוק מה שנשתמש בו כעת. על פי התיאור שנתתי למעלה, $P\left(B\right)=P\left(A\right)\cdot P\left(B|A\right)+P\left(\overline{A}\right)\cdot P\left(B|\overline{A}\right)$ . הנוסחה הזו היא מקרה פרטי של מה שמכונה "נוסחת ההסתברות השלמה", ואתאר אותה במדוייק עוד מעט.

כעת נשתמש בנתונים שידועים לנו ונוכל לחשב בקלות את $P\left(B\right)$ : $P\left(B\right)=\frac{1}{\ln n}\cdot1+\left(1-\frac{1}{\ln n}\right)\cdot x$ . עכשיו נוכל להציב את הכל בנוסחת בייס ולקבל: $P\left(A|B\right)=\frac{\frac{1}{\ln n}}{\frac{1}{\ln n}+\left(1-\frac{1}{\ln n}\right)x}=\frac{1}{1+\left(\ln n-1\right)x}$ . באופן בלתי מפתיע גילינו שההסתברות תלויה גם ב- $n$ וגם ב- $x$ . אם אנחנו רוצים הסתברות גבוהה להצלחה, אנחנו צריכים ש- $x$ יהיה קטן דיו כדי לבטל את האפקט של $\left(\ln n-1\right)$ . למשל, אם אנחנו רוצים הצלחה ב-99 אחוז מהמקרים אנחנו רוצים שיתקיים $\frac{1}{1+\left(\ln n-1\right)x}=\frac{99}{100}$ , כלומר $100=99+99\left(\ln n-1\right)x$ , כלומר $x=\frac{1}{99\left(\ln n-1\right)}$ . באופן כללי כדי להשיג הצלחה ב- $a$ אחוז מהמקרים צריך שיתקיים $x=\frac{1}{a}\cdot\frac{1}{\ln n-1}$ ; אפשר לראות כאן היטב כיצד $x$ מורכב משני מרכיבים – גם ה"קבוע"של $\frac{1}{a}$ שתלוי רק באחוז ההצלחה שאנו שואפים אליו; אבל גם במידע נוסף של גודל התחום שעליו מתבצעת ההגרלה, שבא לידי ביטוי ב- $\frac{1}{\ln n-1}$ .

הבה נעבור כעת לדבר על נוסחת ההסתברות השלמה. בתחילת הפוסט אמרתי שלעתים קל יותר לחשב את ההסתברות המותנית של משהו מאשר את ההסתברות ה"אמיתית"שלנו וראינו את הדוגמה כרגע, עם חישוב ההסתברות שהמבחן יחזיר תשובה חיובית. הסיבה לכך הייתה שלעתים קרובות ההסתברות ניתנת לתיאור באופן הפשוט ביותר באמצעות חלוקה למקרים, ואז ניתן לטפל בכל מקרה בנפרד. נוסחת ההסתברות השלמה מאפשרת לנו לעשות זאת. נניח שאנחנו מחלקים את מרחב המדגם כולו (את כל $X$ ) לאוסף של מאורעות זרים (זרים פירושו שאין להם תוצאה משותפת) $B_{1},B_{2},\dots,B_{k}$ . אז ההסתברות של מאורע $A$ כלשהו היא ההסתברות שהוא יתרחש בהינתן ש- $B_{1}$ יתרחש, כפול ההסתברות ש- $B_{1}$ יתרחש; ועוד ההסתברות שהוא יתרחש בהינתן ש- $B_{2}$ יתרחש, כפול ההסתברות ש- $B_{2}$ יתרחש; וכן הלאה. מכיוון שה- $B$ -ים תופסים את כל מרחב המדגם, מובטח לנו שלא נפספס אף מקרה. בסיכומו של דבר הנוסחה היא $P\left(A\right)=\sum_{i=1}^{k}P\left(A|B_{i}\right)P\left(B_{i}\right)$ . על פניו היא נראית כמו דרך מסובכת יותר לכתוב את $P\left(A\right)$ , אך כאמור – לעתים קרובות הדרך הנוחה ביותר לחשב את $P\left(A\right)$ היא על ידי חלוקה למקרים שמיוצגים על ידי ה- $B_{i}$ .

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

מושג ההסתברות המותנית יכול לשמש אותנו גם להגדרת מושג נוסף שמתאים מאוד לתפיסה האינטואיטיבית שלנו – מאורעות בלתי תלויים. שני מאורעות $A,B$ הם בלתי תלויים, אינטואיטיבית, אם הידיעה על כך שאחד התרחש לא משפיעה על ההערכה שלנו לגבי ההסתברות שהשני יתרחש. למשל, אם אני מטיל שתי קוביות ומקבל 3 בקוביה הראשונה, זה לא משפיע בכלל על ההסתברות שאקבל מספר זוגי בקוביה השניה, כך שהמאורע "בקוביה הראשונה התקבל 3" והמאורע" בקוביה השניה התקבל מספר זוגי" הם בלתי תלויים. פורמלית זה אומר שמתקיים $P\left(A|B\right)=P\left(A\right)$ (ההסתברות ש- $A$ יתקיים, בלי ידע נוסף בעניין, זהה להסתברות ש- $A$ יתקיים אם ידוע לנו ש- $B$ יתקיים). על פי הנוסחה שלנו של $P\left(A|B\right)$ אפשר לראות ש- $A,B$ הם בלתי תלויים אם ורק אם $P\left(A\cap B\right)=P\left(A\right)P\left(B\right)$ , כלומר אם ההסתברות ששניהם גם יחד יתקיימו היא בדיוק מכפלת ההסתברויות שכל אחד יתקיים בנפרד. למי שזוכר את עקרון הכפל בקומבינטוריקה, זה בדיוק העיקרון הזה, וזה גם ממחיש לנו מתי אי אפשר להשתמש בעקרון הכפל – בדיוק כשיש תלות כלשהי בין שני הדברים שאנו "סופרים".

דוגמה יפה לשימוש במושג זה באה מתחום הקריפטוגרפיה – קלוד שנון, אבי תורת האינפורמציה, עסק גם בשאלה איך ניתן לומר על שיטת הצפנה שהיא "מושלמת". הגדרתו היפה היא פשוטה: נניח שיש התפלגות כלשהי על כל הטקסטים שעשויים להיות מוצפנים באמצעות השיטה (וברור שיש כזו – למשל, התפלגות של כל הטקסטים באנגלית) ונסתכל על התפלגות התוצאות שמקבלים מהצפנות בעזרת השיטה. יהי $X$ טקסט אפשרי אחד ו- $Y$ תוצאת הצפנה אפשרית אחת – אז שיטת ההצפנה היא מושלמת אם לכל $X,Y$ שכאלו מתקיים $P\left(X|Y\right)=P\left(X\right)$ , כלומר אם אנחנו מסתכלים רק על $Y$ , זה לא משפר את הידע שלנו שהטקסט המקורי היה $X$ – ההסתברות שהטקסט המקורי היה $X$ זהה בעינינו למה שידענו עליו גם קודם.

בלבול נפוץ אחד הוא בין מאורעות זרים ומאורעות בלתי תלויים. מכיוון שמאורעות זרים מקיימים $A\cap B=\emptyset$ (קבוצה ריקה) אז $P\left(A\cap B\right)=0$ ומכאן ש- $P\left(A\right)=0$ או $P\left(B\right)=0$ אם הם גם מאורעות בלתי תלויים. מכאן עולה ששני מאורעות בעלי הסתברות חיובית אינם יכולים להיות זרים אם הם בלתי תלויים. בדוגמת הטלת הקוביות שלי, התוצאה $\left(3,2\right)$ ("בקוביה הראשונה התקבל 3 ובשניה 2") היא משותפת לשני המאורעות כך שברור שהם אינם זרים.

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

תגים: מתמטיקה תיכונית, נוסחת בייס, תורת ההסתברות
שייך לקטגוריות הסתברות | 4 תגובות »

הסתברות בסיסית – אחד חלקי קומבינטוריקה

29 ביולי, 2010

בפוסטים קודמים תיארתי כמה מושגי בסיס בקומבינטוריקה, וכעת אני רוצה להציג כמה שימושים שלהם; אלא שהמקום הטוב והמעניין ביותר לטעמי להצגת שימושים של המושגים הבסיסיים שהראיתי היא דווקא תורת ההסתברות – שהיא מה שנלמד כיום בבתי הספר, וגם מתקשרת חזק יותר לחיי היום יום שלנו. תורת ההסתברות היא זו שעונה על שאלות כגון "מה הסיכוי שלי לזכות בלוטו?" או "מה הסיכוי של פול התמנון להצליח ולנחש את תוצאות משחקי המונדיאל?" או "מה כדאי לעשות בבעיה של מונטי הול?" אבל, תשאלו, מה הקשר לקומבינטוריקה? ובכן, תורת ההסתברות המתמטית היא תורה רחבה ועשירה מאוד, שמתקשרת לתחומים רבים של המתמטיקה. הרבה מאוד תלוי בשאלה מה בדיוק ההגרלה שאנחנו מבצעים; הגרלות שונות נחקרות בכלים שונים. לא אכנס כרגע לעובי הקורה אלא רק אסתפק בלהגיד שאני הולך לדבר לעת עתה על הגרלות פשוטות מאוד יחסית, שעבורן הקשר לקומבינטוריקה ברור. הקשר הבסיסי הוא זה: אם יש לי קבוצה של $n$ אובייקטים ואני בוחר אחד מהם באקראי (כשלכל איבר יש הסתברות שווה להיבחר), אז ההסתברות שלי להגריל אובייקט אחד ספציפי היא $\frac{1}{n}$ . אם יש 100 תוצאות אפשריות בלוטו, אז ההסתברות שלי לזכות בלוטו (בהינתן שמילאתי טופס יחיד) היא $\frac{1}{100}$ . באופן כללי כשיש לנו בעיה הסתברותית פשוטה שכזו, אנחנו משתמשים בקומבינטוריקה כדי למצוא כמה אובייקטים קיימים בסך הכל ("כמה תוצאות אפשריות יש בלוטו?") ואז ההסתברות שלנו לזכות היא אחד חלקי המספר שמצאנו.

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

תורת ההסתברות מנסה למדל באופן מתמטי סיטואציות "אקראיות". כאן כבר מתחילה הבעיה, שכן אין דרך טובה (מבחינה מתמטית) להגדיר מה זה "אקראי". האם קיום אלוהים הוא אקראי? כלומר, האם ניתן להגיד "בהסתברות $\frac{1}{3}$ אלוהים קיים"? ודאי שלא, הרי מדובר על משהו שהוא או נכון, או שאינו נכון, כלומר ההסתברות שלו היא 0 או 1. גם אמירה כמו "בהסתברות $\frac{1}{2}$ ירד מחר גשם" היא בעייתית – אמנם, אנחנו עוד לא יודעים מה יקרה, אבל אנחנו יודעים שאו שירד גשם, או שלא; אם היינו מסוגלים לחזות את העתיד היינו יודעים בהסתברות 1 שלא יירד גשם מחר – ואז, מה ההגיון מאחורי אמירה כמו "בהסתברות $\frac{1}{2}$ ירד גשם"? לכאורה עולה מכאן שההסתברות תלויה בנקודת המבט שלנו. איך אפשר למדל דבר שכזה?

הדרך האינטואיטיבית לחשוב על הסתברות, אם כן, היא אף פעם לא בתור הסתברות של אירוע בודד, אלא בתור נסיון לענות לשאלה "אם נחזור על אותו ניסוי שוב ושוב באותם תנאים, מה החלק היחסי של המקרים שבהם תתקבל תוצאה כזו וכזו?". אם מטילים קוביה שוב ושוב, אנחנו מצפים שנקבל את התוצאה $1$ בערך ב- $\frac{1}{6}$ מהמקרים – מכאן שההסתברות של תוצאה זו היא $\frac{1}{6}$ . אפשר לתאר זאת פורמלית, אבל אפילו זה לא נדרש מבחינה מתמטית – זוהי רק אינטואיציה.

ההגדרה הפורמלית היא של מושג שנקרא "מרחב הסתברות". מרחב הסתברות בא לתאר "ניסוי" שיכולות להיות לו כמה תוצאות שונות אפשריות; הוא כולל את "מרחב המדגם" שהוא קבוצת כל התוצאות האפשריות, ו"מידת הסתברות", שהיא ערך מספרי שמותאם לכל איבר במרחב המדגם. הדרישה היחידה היא שסכום ההסתברויות של כל התוצאות האפשריות יהיה בדיוק 1. כך למשל עבור הטלת קוביה מרחב המדגם הוא הקבוצה $X=\left\{ 1,2,3,4,5,6\right\}$ (זהו סימון פשוט לקבוצה שאבריה הם המספרים מ- $1$ עד $6$ ), וההסתברות היא $p\left(a\right)=\frac{1}{6}$ לכל $a\in X$ . הנחה חשובה אחת שכן אציין במפורש היא שמרחב המדגם $X$ שלנו הוא סופי; יש רק מספר סופי של תוצאות אפשריות לניסוי. זו דרישה מאוד מגבילה, והסיבה שאני מציין אותה כאן היא שברגע שבו מתירים מרחב מדגם אינסופי התורה מסתבכת פי כמה וכמה. על הסיבוך שמתקבל כשמתירים קבוצה אינסופית "קטנה" (מה שמכונה "קבוצה בת מניה"בניסוח מתמטי יותר מדוייק – קבוצה שאפשר למספר את אבריה ב- $1,2,3,\dots$ וכן הלאה) אני עוד אוכל לדבר ואעשה זאת בהמשך; אבל הסיבוך שמתקבל ברגע שמרחב המדגם הוא קבוצה אינסופית "גדולה" (למשל, קבוצת כל המספרים הממשיים, שניתן להוכיח שאינה בת מניה) כבר לא אדבר כלל כי התורה הופכת להרבה יותר מורכבת (והרבה יותר מעניינת) בשלב זה, ומפסיקה לחלוטין להיות חומר ברמה תיכונית.

ההסתברות של כל תוצאה במרחב המדגם לא חייבת להיות זהה. אין בעיה להגדיר מרחב מדגם שמייצג קוביה "מוטה": $X=\left\{ 1,2,3,4,5,6\right\}$ אבל $p\left(1\right)=\frac{1}{2},p\left(2\right)=\frac{1}{3},p\left(3\right)=\frac{1}{6},p\left(4\right)=p\left(5\right)=p\left(6\right)=0$ . כאן ההסתברויות מאוד לא אחידות, והתוצאות 4,5,6 מיותרות לחלוטין – אין שום סיכוי שהן יצאו.

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

אם כן, מהו מרחב המדגם? מה כאן ההגרלה בכלל? די ברור שהגרלה אחת היא של המיקום של המכונית מאחורי הדלתות – אנחנו מניחים (למרות ששימו לב – זה מעולם לא נאמר במפורש!) שההסתברות היא אחידה לכל אחת מהדלתות. באופן דומה אנחנו מניחים שהבחירה שלנו עצמנו בדלת היא הסתברותית ושלכל דלת אותה הסתברות. לכן אפשר לתאר כל תוצאה במרחב המדגם שלנו כזוג $\left(a,b\right)$ כאשר $a,b$ שניהם מספרים בין 1 ל-3, וההסתברות של כל תוצאה $\left(a,b\right)$ שכזו היא בדיוק $\frac{1}{9}$ .

מהי ההסתברות שהניחוש הראשוני שלנו יהיה נכון ונפגע בדלת הנכונה? פורמלית זהו סכום ההסתברויות של כל התוצאות שבהן הניחוש שלנו זהה לדלת שהוגרלה. במילים אחרות, כל הזוגות $\left(a,b\right)$ שבהם $a=b$ . דרך אחת לכתוב את הקבוצה הזו היא $\left\{ \left(a,b\right)|a=b\right\}$ ("זוגות מהצורה $\left(a,b\right)$ שמקיימים את הקריטריון $a=b$ ). דרך אחרת לכתוב את זה היא בתור $\left\{ \left(a,a\right)|a=1,\dots,3\right\}$ ("זוגות מהצורה $\left(a,a\right)$ כאשר $a$ הוא מספר בין 1 ל-3"). שימו לב שבדרך ההצגה הראשונה בכלל לא טרחתי לציין ש- $a,b$ הם מספרים בין 1 ל-3 אלא השארתי לקורא להבין את זה מההקשר; בדרך ההצגה השניה ציינתי זאת במפורש כי לא נעים לכתוב רק $\left\{ \left(a,a\right)\right\}$ שנראה קצר מדי. אני מתעמק על הנקודה הזו כי כך קורה לעתים קרובות במתמטיקה – קבוצות מוגדרות באופנים "מקוצרים" שמשאירים לקורא חלק מההבנה של ההגדרה.

לקבוצה של תוצאות בסיסיות שכאלו קוראים מאורע. מה שאמרתי כרגע הוא שקבוצת הזוגות מהצורה $\left(a,a\right)$ ניתנת לפרשנות מילולית בתור המאורע "הניחוש ההתחלתי שלנו היה נכון". חלק ניכר מהבעיה עם בעיות מילוליות בהסתברות היא לזהות איזה מאורע מתאים לתיאור מילולי מסויים – לעתים קרובות זה מבלבל הרבה יותר משזה נשמע במבט ראשון.

ההסתברות לכך שמאורע מסויים יתרחש היא בסך הכל סכום ההסתברויות של האיברים שלו. כאן ההסתברות של כל איבר במרחב המדגם היא $\frac{1}{9}$ ובמאורע שדיברנו עליו יש שלושה איברים, ולכן ההסתברות של המאורע הזה היא $\frac{1}{9}+\frac{1}{9}+\frac{1}{9}=\frac{1}{3}$ , ועל כן זו ההסתברות שנקלע למטרה בנסיון הראשון. מכאן אפשר כבר להסיק את יתר הניתוח של מונטי הול – אם אנחנו מחליפים דלת תמיד, אז ההסתברות שנזכה שווה להסתברות שהניחוש הראשון שלנו יהיה שגוי; ואם ההסתברות לכך שהוא יהיה נכון היא $\frac{1}{3}$ , אז ההסתברות לכך שהוא יהיה שגוי היא $1-\frac{1}{3}=\frac{2}{3}$ (כאן אנו מסתמכים על כך שסכום ההסתברויות של כל האיברים במרחב המדגם הוא $1$ , ולכן כדי לדעת את ההסתברות של המאורע "הניחוש הראשוני שלנו היה שגוי"מספיק לחסר מ-1 את ההסתברות של כל האיברים של מרחב המדגם שלא שייכים למאורע הזה. מבחינה מתמטית פורמלית מתארים את זה כך: אם מאורע מסומן ב- $A$ , אז ב- $\overline{A}$ (או לפעמים $A^{c}$ ) מסמנים את המאורע המשלים שלו, של כל אברי מרחב המדגם שאינם ב- $A$ . ואז מתקיימת הנוסחה $p\left(\overline{A}\right)=1-p\left(A\right)$ .

נסכם אם כן את מה שאמרנו עד כה: בהסתברות מגדירים מרחב מדגם שהוא קבוצה $X$ שמייצגת את התוצאות האפשריות של הגרלה כלשהי, כך שלכל $a\in X$ מותאם מספר $0\le p\left(a\right)\le1$ ומתקיים $\sum_{a\in X}p\left(a\right)=1$ (סכום ההסתברויות של כל אברי $X$ הוא 1). לתת קבוצות של $X$ , $A\subseteq X$ קוראים "מאורעות" והסתברותן היא פשוט סכום ההסתברויות של אבריהן: $p\left(A\right)=\sum_{a\in A}p\left(a\right)$ . אפשר גם לדבר על המאורע ה"ריק" שלא מכיל שום איברים – מסמנים זאת בסימן הרגיל שבו מסמנים את הקבוצה הריקה, $\emptyset$ , ומן הסתם $p\left(\emptyset\right)=0$ . זו נקודת המוצא האקסיומטית שמאפשרת דיון מתמטי מדוייק במושגי הסתברות שונים ומשונים שאציג בהמשך. למרות שכל זה פשוט יחסית, האקסיומות הללו הוצעו רק במהלך המאה ה-20 (בעוד שחקר פחות פורמלי של הסתברות בוצע כבר מאות שנים לפני כן).

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

נניח ש- $X$ אינה קבוצה סופית אלא אינסופית; איך אפשר לדבר על סכום איבריה? הקריטריון $\sum_{a\in X}p\left(a\right)=1$ נהיה בעייתי לניסוח. כל עוד $X$ היא בת מניה המצב לא גרוע כל כך כי יש לנו מושג קיים של סכום בן מניה של איברים. אבל אם $X$ היא לא בת מניה (למשל, $X=\mathbb{R}$ ) כל התורה הזו הולכת לפח; לא קשה להראות שכדי שיתקיים $\sum_{a\in X}p\left(a\right)=1$ אז בהכרח רק מספר בן מניה של איברים $a\in X$ יכול לקיים $p\left(a\right)>0$ . כלומר, צריך לזרוק את ההגדרות שאיתן עבדתי עד כה ולהמציא משהו מחוכם יותר. הפתרון הוא לא להגדיר את $p$ לכל איבר ב- $X$ בנפרד, אלא להגדיר את $p$ מראש על תת קבוצות של $X$ ; כלומר, להגדיר את $p$ על מאורעות, ולא סתם על איברים בודדים. למעשה, בהכרח יתקיים שלמרביתם המוחצת של המאורעות שכוללים רק איבר אחד, ההסתברות תהיה 0; זה לא אומר שהאיבר הזה לעולם לא יכול להיבחר, אלא "כמעט אף פעם לא" ייבחר.

כמובן שאי אפשר להגדיר את $p$ באופן שרירותי אלא נדרש הגיון מסויים (למשל, שאם מאורע אחד מכיל מאורע אחר, הסתברותו תהיה גדולה יותר). לפונקציה שמקיימת את ההגיון הזה קוראים "פונקצית מידה" והיא מופיעה במתמטיקה בהקשרים רבים, לא רק של תורת ההסתברות. אחת מהתוצאות הבסיסיות של תורת המידה (שכבר תיארתי בעבר) היא שלא ניתן להגדיר פונקצית מידה "מוצלחת" על כל אברי הישר הממשי. גם בתורת ההסתברות יש בעיה דומה – לרוב לא ניתן להגדיר הסתברות באופן מוצלח על כל תת הקבוצות של $X$ , ולכן בהגדרת מרחב ההסתברות מציינים מראש במפורש מהן הקבוצות שעליהן כן מוגדרת מידה – אוסף קבוצות זה נקרא "מרחב המאורעות" של המרחב ההסתברותי והוא חלק בלתי נפרד מההגדרה. במקרה של $X$ הסופי שעליו דיברתי בפוסט הזה כל הקושי הזה נעלם כי כל תת קבוצה של $X$ ניתנת למדידה באופן שהצגתי ( $p\left(A\right)=\sum_{a\in A}p\left(a\right)$ ) ולכן לא נכנסתי לכל הפרטים הללו.

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

תגים: מבוא למתמטיקה, תורת ההסתברות
שייך לקטגוריות הסתברות | 2 תגובות »

אז אולי רק הראשוניים בטור ההרמוני מתכנסים ל-137?

26 ביולי, 2010

בפרשיית הטרחן הכפייתי והטור ההרמוני שדיווחתי עליה אתמול חלו התפתחויות מרעישות – הטרחן שינה את עמדתו (דבר נדיר למדי), וטענתו החדשה היא שהטור ההרמוני אכן אינו מתכנס ל-137, כי אם מה שנותר מהטור ההרמוני כאשר משאירים בו רק את האיברים שהם הופכיים של ראשוניים. במילים אחרות, הטור $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\dots$ מתכנס ל-137, ובקיצור: $\sum\frac{1}{p}=137$ (זהו סימון מקובל שכן בתורת המספרים נהוג לסמן ב- $p$ מספרים טבעיים ראשוניים).

ובכן, כמו שכבר כתבתי בפוסט של אתמול, גם טור זה מתבדר לאינסוף, והייתי רוצה לנצל את ההזדמנות הזו כדי לתאר את ההוכחה, שהיא פשוטה למדי ומתבססת על רעיון שהוא כה יפה עד שכדאי להזכיר אותו שוב – ההצגה הכפלית של הטור ההרמוני (או יותר במדוייק, ההצגה הכפלית של פונקצית הזטה של רימן). כבר הראיתי אותה בפוסט שהציג את הוכחת אוילר לקיום אינסוף ראשוניים וגם על ההוכחה שאציג כעת אפשר לחשוב בתור הוכחה חזקה עוד יותר לקיום אינסוף ראשוניים, שכן אם היה רק מספר סופי שלהם אז הטור $\sum\frac{1}{p}$ היה סופי ולא יכל להתבדר; למעשה, העובדה שהטור הזה מתכנס מלמדת אותנו משהו על "כמות" הראשוניים. זכרו שטורים כמו $\sum\frac{1}{n^{2}}$ מתכנסים, כך שאנו למדים שהראשוניים נפוצים יותר מאשר מספרים שהם ריבועים. לטעמי זהו רעיון מקסים – היכולת שלנו למדוד "כמות"באמצעות התבדרות של טור.

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

לב ההוכחה הוא במה שכבר כיניתי פעם "הגרסה האנליטית של המשפט היסודי של האריתמטיקה". המשפט היסודי של האריתמטיקה אומר לנו שכל מספר טבעי ניתן להצגה באופן יחיד בתור מכפלה של מספרים ראשוניים (ומן הסתם כל מכפלה של ראשוניים נותנת לנו מספר טבעי). זה מאפשר לנו להציג באופן שונה למדי את הסכום החלקי של הטור ההרמוני, $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$ , באמצעות מכפלה של גורמים שמערבים ראשוניים; כפי שנראה בקרוב, כל עוד אנחנו מנסים להצטמצם לטורים סופיים לא נוכל לתפוס במדוייק את $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}$ אלא רק משהו שתופס גם אותו וגם איברים נוספים; אבל זה לא אכפת לנו.

אם כן, יהיה $n$ מספר טבעי כלשהו, ויהיו $p_{1},p_{2},\dots,p_{\pi\left(n\right)}$ כל הראשוניים הקטנים מ- $n$ ( $\pi\left(n\right)$ הוא מספרם; זהו סימון סטנדרטי). הפאנץ' המרכזי הוא שכל מספר טבעי עד וכולל $n$ הוא מכפלה של חזקות של הראשוניים הללו בלבד; ראשוניים גדולים יותר מן הסתם אינם רלוונטיים כי לא ניתן להגיע על ידי מכפלה שלהם אלו באלו למספר שקטן יותר מהם. כאן מגיע התעלול ודומני שהכי פשוט להציג אותו. נתבונן במכפלה $\lambda\left(n\right)=\frac{1}{1-\frac{1}{p_{1}}}\cdot\frac{1}{1-\frac{1}{p_{2}}}\cdots\frac{1}{1-\frac{1}{p_{\pi\left(n\right)}}}$ . מה יש לנו כאן?

מצד אחד, זוהי מכפלה סופית של מספרים רציונליים, כך שברור שאין כאן שום בעייתיות מבחינת התכנסות וכדומה. מהצד השני אני הולך לעשות להטוט. הבה ונתבונן באיבר הכללי של המכפלה הזו: $\frac{1}{1-\frac{1}{p_{k}}}$ . חלקכם ודאי שמים לב שהיצור הזה דומה לסכום של סדרה הנדסית אינסופית: $1+q+q^{2}+\dots=\frac{1}{1-q}$ כאשר $\left|q\right|<1$ . ובכן, כאן $\left|\frac{1}{p_{k}}\right|<1$ בבירור, שכן $p_{k}\ge2$ ; ולכן $\frac{1}{1-\frac{1}{p_{k}}}=1+p_{k}^{-1}+p_{k}^{-2}+\dots$ . במילים אחרות, את המכפלה שלעיל אפשר לכתוב גם כ:

$\left(1+p_{1}^{-1}+p_{1}^{-2}+\dots\right)\cdots\left(1+p_{\pi\left(n\right)}^{-1}+p_{\pi\left(n\right)}^{-2}+\dots\right)$

יש לנו כאן מכפלה סופית של טורים אינסופיים. על פניו לא ברור האם ניתן "לפתוח" אותה – ואכן, במקרים מסויימים לא ניתן לעשות זאת כי זה מוביל לתוצאות ההרסניות שעליהן מצביע משפט רימן. עם זאת, תוצאה בסיסית בתורת הטורים מראה שניתן "לפתוח"מכפלה כזו במקרה שבו כל הטורים במכפלה מתכנסים בהחלט, כלומר הטור הערכים המוחלטים שלהם מתכנס. מכיווון שכל הטורים המעורבים כאן הם חיוביים וכולם בוודאי מתכנסים, הקריטריון הזה מתקיים מאליו ולכן ניתן לפתוח את הסוגריים. מה המשמעות של פתיחת סוגריים? אנחנו מקבלים סכום שכל איבר בו הוא מכפלה שכוללת איבר אחד מכל אחד מהסוגריים. אם להיות ממש פורמליים, הסכום הוא של איברים מהצורה $p_{1}^{-a_{1}}p_{2}^{-a_{2}}\cdots p_{\pi\left(n\right)}^{-a_{\pi\left(n\right)}}$ לכל וקטור אפשרי $\left(a_{1},a_{2},\dots,a_{\pi\left(n\right)}\right)$ של מספרים שלמים אי שליליים.

כעת, שימו לב שאת המכפלה שלעיל אפשר גם לכתוב בתור $\left(p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{\pi\left(n\right)}^{a_{\pi\left(n\right)}}\right)^{-1}$ וכעת מה שכתוב בתוך הסוגריים הוא פשוט מספר טבעי שהפירוק לגורמים שלו מכיל רק את הראשוניים $p_{1},\dots,p_{\pi\left(n\right)}$ . במילים אחרות, $\lambda\left(n\right)$ (המכפלה שכתבנו בהתחלה) שווה ל- $\lambda\left(n\right)=\sum\frac{1}{k}$ כאשר $k$ רץ על כל המספרים הטבעיים שהפירוק שלהם לגורמים מכיל רק את $p_{1},\dots,p_{\pi\left(n\right)}$ – וכאמור, זה מכיל גם את כל הטבעיים הקטנים או שווים ל- $n$ , אבל גם דברים גדולים יותר (למשל, חזקות גדולות של 2 שעוברות את $n$ ). במילים אחרות, מה שאנחנו יכולים בודאות לכתוב הוא $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}\le\lambda\left(n\right)$ . מכיוון שהטור ההרמוני מתבדר, כפי שראינו בפוסט הקודם, נובע מכך שכאשר משאיפים את $n$ לאינסוף, $\lambda\left(n\right)$ שואף לאינסוף. שימו לב שכרגע הוכחנו שוב את קיומם של אינסוף ראשוניים (כי אם היה מספר סופי, אז $\lambda\left(n\right)$ היה הופך לקבוע החל ממקום מסויים).

עד כאן הכל טוב ויפה, אבל איך $\lambda\left(n\right)$ המדובר קשור לטור ההרמוני כאשר משאירים בו רק את הראשוניים? אמנם, הוא מיוצג בדרך אחת כמכפלה של ראשוניים, אבל זה בדיוק העניין – הם מכפלה, לא סכום. כאן נחלץ לעזרתנו כלי בסיסי נוסף במתמטיקה – הלוגריתם. לוגריתם הופך מכפלות לסכומים בצורה "יפה" שמאפשרת את המשך הטיפול בהם, ולכן העניין שלנו עובר כעת מ- $\lambda\left(n\right)$ עצמו אל $\ln\lambda\left(n\right)$ . שימו לב שאם $\lambda\left(n\right)\to\infty$ כך ש- $\ln\lambda\left(n\right)\to\infty$ (כי $\ln\left(n\right)\to\infty$ ). כעת בואו וננסה להבין אך $\ln\lambda\left(n\right)$ נראה – וכמו שכבר הבנתם שאנחנו עושים כל הזמן לא באמת נמצא את הצורה המדוייקת שלו, כי זה קשה, אלא חסם. במקרה זה, חסם עליון. ברשותכם, אעבור להשתמש בסימון מתמטי עוד יותר קומפקטי מזה שהשתמשתי בו עד כה:

$\ln\lambda\left(n\right)=\ln\left(\prod\left(1-p_{k}^{-1}\right)^{-1}\right)=\sum\ln\left(1-p_{k}^{-1}\right)^{-1}=-\sum\ln\left(1-p_{k}^{-1}\right)$

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

כאן נכנס לתמונה להטוט מתמטי אחר – טור טיילור. לא אוכיח זאת כרגע, אבל באופן כללי ידוע כי $\ln\left(1-x\right)=-\sum_{m=1}^{\infty}\frac{x^{m}}{m}$ כאשר $\left|x\right|<1$ . כאן $x=p_{k}^{-1}$ ולכן ניתן להשתמש בתוצאה הזו. מקבלים:

$-\sum_{k=1}^{\pi\left(n\right)}\ln\left(1-p_{k}^{-1}\right)=\sum_{k=1}^{\pi\left(n\right)}\sum_{m=1}^{\infty}\frac{p_{k}^{-m}}{m}$

עכשיו כבר יש לנו סכום כפול מפלצתי באגף ימין ולא ברור איך אנחנו הולכים להיחלץ מהצרה הזו, אבל עכשיו מגיע הקסם האחרון: את הסכום הזה אפשר לחלק לשני סכומים, כשאחד הוא בדיוק מה שמעניין אותנו והשני הוא חסר חשיבות. שימו לב שכאשר $m=1$ מקבלים באגף שמאל איברים מהצורה $p_{k}^{-1}$ . אם כן, אפשר לכתוב:

$\sum_{k=1}^{\pi\left(n\right)}\sum_{m=1}^{\infty}\frac{p_{k}^{-m}}{m}=\sum_{k=1}^{\pi\left(n\right)}\frac{1}{p_{k}}+\sum_{k=1}^{\pi\left(n\right)}\sum_{m=2}^{\infty}\frac{p_{k}^{-m}}{m}$

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

$\sum_{m=2}^{\infty}\frac{p_{k}^{-m}}{m}<\sum_{m=2}^{\infty}p_{k}^{-m}=p_{k}^{-2}\left(\sum_{m=0}^{\infty}p_{k}^{-m}\right)=p_{k}^{-2}\left(1-p_{k}^{-1}\right)^{-1}<2p_{k}^{-2}$

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

במילים אחרות, מה שהצלחנו להראות הוא את התוצאה הבאה:

$\ln\lambda\left(n\right)<\sum_{k=1}^{\pi\left(n\right)}\frac{1}{p_{k}}+2\sum_{k=1}^{\pi\left(n\right)}\frac{1}{p_{k}^{2}}$ . מה קורה כאשר משאיפים את $n$ לאינסוף? ובכן, הטור $\sum_{k=1}^{\infty}\frac{1}{p_{k}^{2}}$ הוא טור מתכנס (כי $\sum\frac{1}{n^{2}}$ מתכנס). ומצד שני, כבר אמרנו כי $\ln\lambda\left(n\right)$ שואף לאינסוף ולכן אגף ימין של אי השוויון חייב לשאוף לאינסוף בעצמו; מכאן ש- $\sum_{k=1}^{\pi\left(n\right)}\frac{1}{p_{k}}$ חייב לשאוף לאינסוף, דהיינו $\sum_{k=1}^{\infty}\frac{1}{p_{k}}$ מתבדר, וזה מה שהיה צריך להוכיח.

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

תגים: תורת המספרים האנליטית, טורים מתבדרים, טכני, הטור ההרמוני, הוכחות יפות
שייך לקטגוריות אנליזה מתמטית, תורת המספרים | 6 תגובות »

האם הטור ההרמוני מתכנס ל-137?

25 ביולי, 2010

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

מה הלך כאן? נניח שאורך החדר הוא 1. המתמטיקאי הראשון תיאר את מעבר החדר כסדרה של "צעדים", שבה בכל צעד עוברים את חצי הדרך שעברנו בצעד הקודם. כלומר, אחרי צעד אחד עברנו $\frac{1}{2}$ , אחרי שניים עברנו $\frac{1}{2}+\frac{1}{4}$ , אחרי שלושה עברנו $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}$ וכן הלאה. הסכומים הללו הם מקרים פרטיים של טור הנדסי ולכן קיימת לנו נוסחה פשוטה שנותנת את ערכם: $1-\frac{1}{2^{n}}$ הוא המרחק שנעבר עד וכולל הצעד ה- $n$ (למי שאינו מאמין – שיציב $n=1,2,3$ בנוסחה וישווה זאת לסכומים שכתבתי למעלה). לא קשה לראות שלא משנה איזה ערך של $n$ אציב בנוסחה הזו לא אוכל לקבל 1, כך שהמתמטיקאי הראשון לא יגיע אף פעם אחרי מספר סופי של צעדים אל הקצה השני של החדר (באופן המאוד מוזר שבו אנחנו בוחרים למדוד "צעדים"). מה שהשני אומר הוא שאנחנו לא באמת חייבים להגיע ל-1 כדי לקטוף את הפירות של מעבר החדר; נניח שכל מה שאנחנו צריכים הוא שהמרחק בינינו ובין הבחורה יהיה $0.0000001$ ; אז לא קשה למצוא $n$ שהוא גדול כל כך עד שהמרחק שלנו מהבחורה קטן מה- $0.0000001$ הזה (תרגיל למשועממים – מצאו $n$ שכזה). על סיטואציה שכזו אומרים שהסדרה $1-\frac{1}{2^{n}}$ שואפת ל-1; היא לא בהכרח מגיעה ל-1, אבל לכל רמת קרבה שרק נרצה שהיא תתקרב בה ל-1 מבלי שתגיע אליו ממש, מובטח לנו שמתישהו זה יקרה (התנאי המדוייק שמגדיר שאיפה למספר כלשהו הוא טיפה יותר מורכב וכבר פירטתי עליו בעבר).

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

נניח שכעת אנחנו מנסים למדוד את צעדינו באופן הבא: בצעד הראשון נפסע מרחק של 1. בשני מרחק של $\frac{1}{2}$ . בשלישי מרחק של $\frac{1}{3}$ ; ברביעי מרחק של $\frac{1}{4}$ ובאופן כללי, בצעד ה- $n$ נפסע מרחק של $\frac{1}{n}$ . די ברור שאחרי צעד אחד כבר נעבור מרחק של 1; גם ברור שאחרי ארבעה צעדים נעבור מרחק של 2, אבל מכאן ואילך המאמץ שנדרש מאיתנו כדי לעבור את 3 הוא גדול למדי, והמאמץ לעבור את 4 גדול עוד יותר, וכן הלאה וכן הלאה. אם כן, מה המספר המקסימלי שעוד נצליח לעבור? איזה חדר הוא גדול מספיק כדי שלא נוכל להגיע לקצה השני שלו? זו השאלה שלפנינו. בניסוח פורמלי, מדברים על הסכום $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}+\dots$ , שמכונה "הטור ההרמוני"ונכתב בקיצור כ- $\sum_{n=1}^{\infty}\frac{1}{n}$ ושואלים מהו סכום הטור הזה – למה הוא שואף באותו מובן של קודם.

כאן אפשר לחלק את בני האדם לשלושה סוגים: יש את אלו שאומרים שמובן מאליו שסכום הטור יהיה אינסוף כי יש בו אינסוף איברים. אלא שכבר ראינו דוגמה לטור שבו הטענה הזו שגויה בתכלית – $\sum_{n=1}^{\infty}\frac{1}{2^{n}}$ שעליו דיברנו קודם מתכנס ל-1 ולא לאינסוף. לכן מי שטוען שהטור אינסופי מסיבה זו פשוט אינו "משתתף במשחק" שלנו ואינו דובר את אותה שפה כמונו; כבר עסקתי פעם בבלוג באדם מסוג זה.

הסוג השני, המתמטיקאי, יגיד שסכום הטור הזה הוא אינסוף, אבל שהדבר אינו מובן מאליו כלל וכלל, ויש להוכיח זאת. והוא גם יציג הוכחה או שתיים. אני מתעתד לעשות זאת בפוסט הזה. כדי להבהיר עד כמה הטענה הזו בלתי מובנת מאליה רק אעיר שעבור הטור $\sum_{n=1}^{\infty}\frac{1}{n^{\alpha}}$ כאשר $\alpha$ הוא מספר ממשי כלשהו הגדול ממש מ-1 ( $\alpha>1$ ), הטור כן מתכנס ("מתכנס"פירושו שסכומו קטן מאינסוף). כלומר, $\sum_{n=1}^{\infty}\frac{1}{n}$ הוא "כמעט" מתכנס וזה לא מובן כלל מאליו שהוא מתקלקל כך.

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

הבה ונעבור להסבר מדוע הטור אינו מתכנס. ראשית, אינם חייבים לסמוך עלי – במהלך הדיון בפורום ניתן קישור למאמר שמציג 20 הוכחות שונות לתוצאה הזו. שנית, צריך להסביר מה בעצם אני מנסה להוכיח. לומר שהטור מתכנס לאינסוף פירושו (במקרה הספציפי הזה; ההגדרה הכללית היא מעט יותר מסובכת) שלכל מספר טבעי $k$ שרק תגידו לי, אוכל לתת לכם מספר איברים כלשהו $n$ כך שאחרי שסוכמים $n$ איברים מקבלים סכום שגדול מ- $k$ . למשל, עבור $k=137$ , שהוא הסכום המשוער שהזכרתי קודם, אפשר לראות שאם נסכום $2^{300}$ איברים נקבל תוצאה שגדולה מ-137. איך? למה? מאיפה המספר הזה הגיע? זה מה שנראה עכשיו. ראשית כל, הנה המחשה ציורית של ההוכחה, שמציגה בבירור את הרעיון המרכזי בה – קיבוץ איברים:

$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\dots>$

$1+\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)+\dots=$

$1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\dots$

כעת נעבור לתיאור יותר מדויק של מה שקורה כאן. לצורך נוחות, הבה ונסמן ב- $H_{n}$ את מה שמקבלים אחרי שסוכמים את $n$ האיברים הראשונים של הטור. המספר הזה נקרא "המספר ההרמוני ה- $n$ -י". לא קל לחשב במדוייק את הערכים של ה- $H_{n}$ -ים ולכן במקום זה נותנים להם חסם תחתון – משהו שמובטח ש- $H_{n}$ יהיה גדול ממנו. ההוכחה הפשוטה ביותר לכך שהטור ההרמוני אינו מתכנס, שנמצאה כבר במאה ה-14, מתבססת על שיטה פשוטה ויפה לתת חסם תחתון ל- $H_{n}$ -ים: נסתכל רק על ה- $n$ -ים שהם חזקות של 2, כלומר $H_{2^{n}}$ , לכל $n\ge0$ . כדי לקבל תחושה, הבה ונתבונן באיברים הראשונים:

$H_{2^{0}}=1$

$H_{2^{1}}=1+1\cdot\frac{1}{2}$

$H_{2^{2}}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}>1+\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)=1+2\cdot\frac{1}{2}$

רגע, רגע, רגע – מה עשינו עבור $H_{2^{2}}$ ? ויתרנו על חישוב מדוייק שלו ובמקום זה הלכנו על חסם תחתון. אמרנו שאפשר לקחת את $\frac{1}{3}+\frac{1}{4}$ ולהשתמש בשיקול הבא: $\frac{1}{3}$ הוא גדול מ- $\frac{1}{4}$ ולכן $\frac{1}{3}+\frac{1}{4}>\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$ . הצמצום הזה עוזר לנו לחשב את החסם. כדי לראות זאת יותר בבירור הבה ונסתכל על המספר ההרמוני הבא בתור:

$H_{2^{3}}=H_{2^{2}}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}>H_{2^{2}}+4\left(\frac{1}{8}\right)>1+2\cdot\frac{1}{2}+\frac{1}{2}=1+3\cdot\frac{1}{2}$

מה עשינו כאן? אמרנו ש- $H_{2^{3}}$ שווה בדיוק ל- $H_{2^{2}}$ ובנוסף כל האיברים ה"חדשים" שלא הופיעו ב- $H_{2^{2}}$ – שהם כל האיברים מהצורה $\frac{1}{k}$ עבור $2^{2}<k\le2^{3}$ . זה כבר מכתיב לנו את הדרך למקרה הכללי: נניח שהוכחנו ש- $H_{2^{k}}\ge1+\frac{k}{2}$ ואנחנו רוצים למצוא חסם על $H_{2^{k+1}}$ , מה עושים? ראשית, כותבים $H_{2^{k+1}}=H_{2^{k}}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\dots+\frac{1}{2^{k+1}}$ . כעת, הסכום $\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\dots+\frac{1}{2^{k+1}}$ כולל בדיוק $2^{k+1}-2^{k}=2^{k}$ איברים, והאיבר הקטן ביותר מביניהם הוא $\frac{1}{2^{k+1}}$ , כך שאנו מקבלים את החסם $H_{2^{k+1}}\ge H_{2^{k}}+\frac{2^{k}}{2^{k+1}}\ge1+\frac{k}{2}+\frac{1}{2}=1+\frac{\left(k+1\right)}{2}$ . בעצם הוכחנו כאן באינדוקציה שלכל $k$ טבעי מתקיים $H_{2^{k}}\ge1+\frac{k}{2}$ , וזהו זה – עבור $k$ גדול מספיק אפשר לעבור כל מספר טבעי שמפריע לנו.

נחזור לדוגמת ה-137: עבור $k=300$ מקבלים $H_{2^{300}}\ge1+\frac{300}{2}=151$ . כך שלמעשה, $2^{300}$ הוא מספר גדול מדי של איברים; אפשר היה להסתפק בהרבה פחות. כמה פחות? בדיוק פתרון המשוואה $1+\frac{k}{2}>137$ , ובמילים אחרות – $k=273$ . אם כן, הוכחנו שהטור ההרמוני עובר את 137 ב- $H_{2^{273}}$ , ובאותה דרך בדיוק נוכל לרמוס כל טענה שהטור ההרמוני מתכנס לסכום סופי אחר.

לאלו מכם שאינם מפחדים מלוגריתמים ואסימפטוטיקה, זוהי הזדמנות לראות שההוכחה הזו גם אומרת לנו משהו על קצב הגידול של $H_{n}$ : אם $n=2^{k}$ אז $k=\lg n$ ולכן $H_{n}\ge1+\frac{\lg n}{2}=\lg\left(2\sqrt{n}\right)$ . למעשה, זה חסם תחתון די גרוע – המספרים ההרמוניים מתנהגים בערך כמו $\ln\left(n\right)$ (ועוד תיקון כלשהו).

ההוכחה הבאה שאציג היא לטעמי לא פחות מיפהפיה, ומספקת הדגמה נוספת לאופן שבו שימוש באקספוננט יכול לפשט בעיות חיבוריות על ידי הפיכתן לכפליות (מוטיב נפוץ למדי בתורת המספרים…). הרעיון הוא לא לחשב את $H_{n}$ ישירות, אלא את $e^{H_{n}}$ (כאשר $e^{x}$ היא פונקצית האקספוננט שכתבתי עליה לא מזמן). גם כאן נצטרך לבצע קירוב כלשהו כדי לקבל נוסחה יפה, ונשתמש בכך ש- $e^{x}>1+x$ לכל $x>0$ (אי השוויון מובן מאליו אם זוכרים ש- $e^{x}=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\dots$ – פשוט לקחנו את שני האיברים הראשונים).

ובכן: $e^{H_{n}}=e^{\sum_{k=1}^{n}\frac{1}{k}}=\prod_{k=1}^{n}e^{\frac{1}{k}}>\left(1+1\right)\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)\cdots\left(1+\frac{1}{k}\right)=2\cdot\left(\frac{3}{2}\right)\cdot\left(\frac{4}{3}\right)\cdots\left(\frac{k+1}{k}\right)=k+1$ .

השורה האחת הזו מסיימת את הסיפור. למי שלא הבין את המעבר שבו נעלמים הפלוסים - $1+\frac{1}{k}=\frac{k+1}{k}$ באופן כללי, ולכן כאן מתקבל $1+\frac{1}{2}=\frac{3}{2}$ וכן הלאה. המעבר האחרון נובע מכך שהמכפלה שקיבלנו היא "מכפלה טלסקופית" שבה כל איבר מצמצם את האיבר הבא: $2\cdot\frac{3}{2}=3$ , ו- $3\cdot\frac{4}{3}=4$ וכן הלאה.

הוכחה אלגנטית ומקסימה נוספת מתבצעת בשלילה: מניחים שהטור ההרמוני אכן מתכנס למספר ממשי $S$ כלשהו, ומשתמשים במניפולציות שמותר לבצע על טורים מתכנסים כדי להגיע לסתירה. הרעיון פשוט: אם $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots=S$ אז אפשר לכפול את שני האגפים בחצי ולקבל $\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}+\dots=\frac{S}{2}$ . שימו לב שבאגף שמאל יש לנו בדיוק את האיברים ה"זוגיים"של הטור ההרמוני והם מתכנסים בדיוק למחצית מסכום הטור ההרמוני. מסקנה? גם האיברים הנותרים, האי זוגיים, מתכנסים למחצית הטור ההרמוני, כלומר $1+\frac{1}{3}+\frac{1}{5}+\dots=\frac{S}{2}$ . אלא מה? כל איבר בטור האי זוגיים גדול ממש מהאיבר המתאים לו בטור הזוגיים: $1>\frac{1}{2}$ , $\frac{1}{3}>\frac{1}{4}$ וכן הלאה. על כן לא ייתכן שסכום שני הטורים זהה – ההפרש חייב להיות לפחות $\frac{1}{2}$ ! (כי ההפרש בין שני האיברים הראשונים הוא $\frac{1}{2}$ והאיברים הבאים רק מגדילים אותו).

הערה או שתיים לסיום החלק המתמטי. ראשית, חבל להזכיר את התבדרות הטור ההרמוני בלי להזכיר הקשר רחב יותר שבו הטור ההרמוני מופיע – פונקצית הזטה של רימן, שמוגדרת כ- $\zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}$ עבור $s>1$ (ובאופן יותר מחוכם עבור ערכים אחרים של $s$ , כולל מרוכבים). התבדרות הטור ההרמוני מראה כי $\zeta\left(1\right)=\infty$ , ואפשר לנצל את התופעה הזו, למשל, כדי להוכיח (בצורה מסובכת יחסית, אמנם) את קיומם של אינסוף ראשוניים; ווריאציה מחוכמת על ההוכחה הזו מובילה למשפט דיריכילה על ראשוניים בסדרות חשבוניות. בקיצור, מדובר בנושא מעניין.

עוד דבר הוא שיש דברים "חלשים יותר" מהטור ההרמוני שעדיין מתבדרים. הדוגמה הקלאסית היא הטור $\sum\frac{1}{p}$ שבו משתתפים רק אותם איברים של הטור ההרמוני שמתאימים למספרים ראשוניים. במובן מסויים זה מראה כי יש כמות "אינסופית גדולה יחסית"של ראשוניים (ומצד שני, כדאי לזכור שכמות הראשוניים איננה מאותו סדר גודל של כמות הטבעיים אלא בערך לוגריתמית).

אוקיי, בואו נעבור לטרחנות. כאמור. מה אפשר לומר על מי שטוען שהטור מתכנס? ראשית, צריך לברר איתו האם הוא מדבר על אותו מושג התכנסות כמונו. יש תורה עשירה ויפה שעוסקת בטורים שמתבדרים על פי ההגדרה הקלאסית, אבל קיימות הגדרות מוכללות להתכנסות שעל פיהן הם אכן מתכנסים. כך למשל הטור $1-1+1-1+1-\dots$ הידוע לשמצה אינו מתכנס בהגדרה הקלאסית, אך כן יש משמעות מסויימת לאמירה שסכומו הוא $\frac{1}{2}$ (לא אכנס לכך כעת, אבל אינטואיציה כפולה: ראשית, הסכומים החלקיים של הטור הם $1,0,1,0,\dots$ והממוצע שלהם הוא $\frac{1}{2}$ ; שנית, אם מפתחים את $\frac{1}{1-x}$ לטור פורמלי מקבלים $1+x+x^{2}+\dots$ וכשמציבים $x=-1$ מקבלים את הטור המדובר, וכשמציבים ב- $\frac{1}{1-x}$ את הערך $x=-1$ מקבלים $\frac{1}{2}$ ).

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

ויש עוד אגדה, והיא טוענת שאין מספר גבול, לסכום מספרי תג שאין להם סוף.

"מספרי תג" בהקשר זה הם פשוט הופכיים של מספרים טבעיים. כלומר, $n^{\prime}=\frac{1}{n}$ . דומני שהסימון הזה איננו המצאה של עצבר, אך בכל מקרה הוא איננו סטנדרטי ואין שום טעם להשתמש בו בהקשר הנוכחי. זו המחשה להבדלי הטרמינולוגיות בין המתמטיקאי והטרחן – בין מי שרוצה שיבינו אותו, ובין מי שלא ברור מה הוא רוצה. כמובן שגם הדיבורים על "אגדה" אינם מבשרים טובות.

הטיעון נמשך ב:

אני מחזיק בדעה כי הטור ההרמוני מתכנס, והשערתי היא שהוא מתכנס ל 137.

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

ההוכחה הזו הופכת דעכן לטור מונוטני, אבל הפיכה זו אינה אפשריתזו אינה הוכחה.

א.עצבר.

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

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

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

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

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

לוי: הדעכן ההרמוני הזה 2' 3' 4' 5' 6' 7' 8'מתחיל עם מספרי הדעיכה הבאים 66.0 75.0 8.0 0.833 0.86 0.87

ראובן: אני רואה שמספר הדעיכה מתחיל ב 0.66 והוא נוסק לעבר 1

לוי: אם מספר הדעיכה ישאר 0.66 יש נוסחה לחישוב הסכום

ואם מספר הדעיכה יגיע ל 0.75 וישאר קבוע, יש נוסחה לחישוב הסכום

ואם מספר הדעיכה יגייע ל 0.8 וישאר קבוע, יש נוסחה לחישוב הסכום

לכן, שינוי מספר הדעיכה לא משנה את העובדה שיש לדעכן מספר סכום, אבל כאשר מספר הדעיכה משתנה, אין לנו נוסחה לחישוב הסכום.

מה שמכונה "מספרי דעיכה" הם היחסים בין איברים עוקבים בסכום. אכן, $\frac{1}{3}/\frac{1}{2}=0.66\dots$ , ו- $\frac{1}{4}/\frac{1}{3}=0.75\dots$ וכן הלאה. עוד אומר עצבר נכון שאם "מספר הדעיכה" של טור הוא קבוע, אז הטור מתכנס – זו דרך מסובכת להציג את המושג המוכר של טור הנדסי מתכנס. למעשה, צריך להיות מדוייקים – "מספר הדעיכה"של הטור צריך להיות קבוע וקטן מ-1 (הטור $1+2+4+8+\dots$ הוא טור הנדסי בעל "מספר דעיכה" 2 והוא אינו מתכנס). אלא שעצבר מבצע כעת קפיצה מחשבתית איומה: המחשבה שאם עבור מספר דעיכה קבוע הטור מתכנס תמיד, זה אומר גם שעבור מספר דעיכה משתנה הטור מתכנס תמיד – טענה שגויה לחלוטין. והוא עוד מגדיל לעשות ואומר:

כל דעכן דועך אל האפס,יש דעכן הדועך אל האפס במספר דעיכה קבוע

ויש דעכן הדועך אל האפס במספר דעיכה משתנה

ואיזה הבדל עקרוני יכול להיות בינהם ?

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

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

שגיאה דומה (אבל בלבוש ערמומי יותר) צצה במקומות רבים במתמטיקה שבהם משתמשים באינסוף. אתן דוגמה או שתיים. ראשית, נניח שיש לנו סדרה $a_{n}$ , ומתקיימת התכונה שלכל $n$ טבעי, מתקיים $\inf\left\{ a_{1},a_{2},\dots,a_{n}\right\} >0$ , כלומר האינפימום של $n$ האיברים הראשונים בקבוצה הוא גדול מאפס. האם ניתן להסיק מכך שהאינפימום של הקבוצה כולה גדול מאפס? בפירוש לא, והסדרה $a_{n}=\frac{1}{n}$ מראה זאת בבירור (מה שכן ניתן לעשות הוא לומר שהאינפימום של הקבוצה כולה הוא גדו או שווה לאפס).

דוגמה מתחום שונה לגמרי – בתורת החישוביות מראים כי כל שפה שיש בה רק מספר סופי של מילים היא כריעה (שפה היא קבוצת מילים; להכריע שפה פירושו להריץ אלגוריתם שבהינתן מילה תמיד מסיים את ריצתו עליה ואומר אם היא שייכת לשפה או לא). עכשיו בואו ניקח שפה $L$ כלשהי ונסתכל על $L_{n}$ – כל המילים ב- $L$ שאורכן לכל היותר $n$ . אז כל $L_{n}$ שכזו היא כריעה, אבל זה ממש לא אומר ש- $L_{\infty}$ (שהיא בעצם $L$ ) תהיה גם כן כריעה, כי ייתכן מאוד ש- $L$ המקורית לא הייתה כריעה. כאן שוב הזינוק מ- $n$ עד לאינסוף הורס לנו את הכל. האינסוף הוא יצור חמקמק.

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

תגים: טרחנים מתמטיים, טורים מתבדרים, הפרדוקסים של זנון, הטור ההרמוני
שייך לקטגוריות אנליזה מתמטית, הבלים פסאודו-מתמטיים | 17 תגובות »

כל כך קשה לבחור…

8 ביולי, 2010

אני ממשיך את סדרת הפוסטים שלי על קומבינטוריקה ברמה תיכונית, והפעם אני רוצה לנקוט בגישה "מתמטית" לדברים שכבר גילינו. המתמטיקאי תמיד מנסה לבחון מחדש את ההנחות שלו ולהקל על הדרישות בכדי להכליל את התוצאות שלו, וזה גם מה שאני רוצה לעשות. הנוסחה המרכזית שגילינו עד כה הייתה כי $\frac{n!}{k!\left(n-k\right)!}$ , שאותו סימנו בקיצור ${n \choose k}$ וכינינו "מקדם הבינום"(מסיבות שהסברתי בפוסט קודם) הוא מספר הדרכים לבחור $k$ מתוך $n$ עצמים. אלא שכאן יש לי שתי הנחות סמויות: שהבחירה היא ללא החזרה, וללא חשיבות לסדר. בפוסט הזה אנסה להסביר מה זה אומר, ומה מקבלים כשמשחקים עם ההנחות הללו.

בואו נזכור מה ${n \choose k}$ אומר באמצעות דוגמה: בלוטו, אם נשכח לרגע מהמספר הנוסף, נבחרים שישה מספרים מתוך 49. הבחירה הזו היא ללא חשיבות לסדר: אם המכונה הגרילה קודם כל את 1 ואז את 2, זו אותה הסיטואציה מבחינתנו כמו זו שבה המכונה הגרילה קודם כל את 2 ורק אז את 1. די ברור שאם הייתה חשיבות לסדר, המשחק היה הופך לקשה פי כמה, כי לא היה מספיק לנחש מי יזכה; היה צריך לנחש גם באיזה סדר הם יופיעו.

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

הנה תרגיל בקומבינטוריקה: אם סוגי הבחירות השונות נקבעים לפי השאלות א) האם יש חשיבות לסדר או לא ו-ב) האם יש החזרה או לא, כמה סוגי בחירות יש? התשובה היא כמובן 4 (מעקרון הכפל). הבה ונטפל בכולן. בכל המקרים יהיה מדובר על בחירה של $k$ אובייקטים כשיש $n$ אובייקטים לבחור מהם.

ובכן, בחירה בלי החזרה ובלי חשיבות לסדר היא כמו שראינו ${n \choose k}$ . לפעמים משתמשים גם בסימון המבלבל $C_{n}^{k}$ וקוראים לזה "צירופים", אך זה הרבה פחות מקובל במתמטיקה ואני לא משתמש בסימונים הללו אף פעם.

נעבור לבחירה בלי החזרה אך עם חשיבות לסדר, מה שנקרא לעתים בעברית "חליפות"ומסומן ב- $A_{n}^{k}$ . הדרך לחשב את מספר האפשרויות לבחור בלי החזרה ועם חשיבות לסדר $k$ מתוך $n$ עצמים היא פשוטה למדי כי אפשר לחשוב עליה כתהליך דו-שלבי: קודם כל נבחר $k$ עצמים מתוך ה- $n$ בלי חשיבות לסדר, ואז נבחר את האופן שבו "מסדרים"אותם. כבר ראינו שיש ${n \choose k}$ אפשרויות לבחור את העצמים בלי חשיבות לסדר, ושבהינתן $k$ עצמים יש $k!$ דרכים לסדר אותם, כך שהתוצאה היא ${n \choose k}k!=\frac{n!}{k!\left(n-k\right)!}k!=\frac{n!}{\left(n-k\right)!}$ . אפשר גם להגיע לתוצאה הזו בדרך ישירה: בהתחלה יש לנו $n$ איברים לבחור מהם, אחר כך יש לנו $n-1$ איברים, אחר כך $n-2$ וכן הלאה… עד שבסופו של דבר יש לנו $n-k$ איברים ואז אנחנו כבר לא בוחרים. נקבל את המכפלה $n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdots\left(n-k+1\right)$ (ה- $+1$ בסוגר האחרון נובע מכך שהבחירה האחרונה מתבצעת רגע לפני שאנו נשארים עם $n-k$ איברים) – לא קשה לראות שמכפלה זו אכן שווה ל- $\frac{n!}{\left(n-k\right)!}$ , אבל היא יותר מסורבלת לכתיבה. שימו לב, אגב, שאם היינו בוחרים $k=n$ היינו מקבלים את התוצאה $n!$ – כלומר, הכללנו גם את הרעיון של סידור $n$ איברים בשורה.

אני רוצה להציג עוד נקודת מבט שתכליל הן את הצירופים והן את החליפות, ותיתן לנו עוד נוסחה מאוד פופולרית. בואו נחשוב לרגע שיש לנו $n$ כדורים, ש- $k$ מתוכם אדומים והיתר כחולים, ואנחנו שואלים את עצמו בכמה דרכים ניתן לסדר אותם בשורה. שימו לב שכל הכדורים מאותו צבע נראים לנו זהים – אם נחליף את המקומות של שני כדורים בעלי אותו צבע נקבל תוצאה שנראית לנו זהה לקודמת, ולכן אין צורך לספור אותה שוב. מה עושים? דרך אחת היא זו: ראשית נחשוב על כל הכדורים כעל אובייקטים שונים זה מזה, ואז יש $n!$ דרכים שונות לסדר אותם בשורה. כעת צריך "לתקן"את הספירות הכפולות שביצענו, והדרך לעשות זאת היא לספור בכמה דרכים שונות ניתן לשנות את הסדר הפנימי בין הכדורים האדומים, ובכמה דרכים שונות ניתן לשנות את הסדר הפנימי בין הכדורים הכחולים, ולחלק בתוצאה זו. יש $k$ כדורים אדומים ולכן $k!$ סידורים פנימיים שלהם, ובאופן דומה יש $\left(n-k\right)!$ סידורים פנימיים של הכדורים הכחולים, ולכן התוצאה היא $\frac{n!}{k!\left(n-k!\right)}$ – בדיוק ${n \choose k}$ וזה לא כל כך מפתיע כי אפשר לחשוב על הסידור הנ"ל כעל "בחר $k$ מקומות עבור הכדורים האדומים ושים את הכחולים ביתר". למעשה, הגישה הזו הייתה האופן שבו הוכחתי את הנוסחה עבור ${n \choose k}$ מלכתחילה.

כעת להכללה המבוקשת – מה קורה אם יש לי כדורים אדומים, ירוקים, צהובים וכחולים? ומה אם יש עוד צבעים? באופן כללי אפשר לחשוב על כך ש- $n$ האיברים מתחלקים לקבוצות, כך שמספרי האיברים בקבוצות הם $k_{1},k_{2},\dots,k_{t}$ . קבוצה יכולה להכיל גם איבר בודד; לכן אנחנו יכולים להניח שה- $k$ -ים מתארים את כל האיברים, כלומר מתקיים $n=k_{1}+k_{2}+\dots+k_{t}$ . על פי אותו הגיון שתיארתי קודם, מספר הסידורים האפשריים בשורה של האיברים הללו, כשאנחנו מתעלמים מהסידורים הפנימיים בין איברים מאותו צבע, הוא $\frac{n!}{k_{1}!k_{2}!\cdots k_{t}!}$ . שימו לב ש- ${n \choose k}$ מתאים למקרה בו יש לנו בדיוק שתי קבוצות, ואילו מספר החליפות, $\frac{n!}{\left(n-k\right)!}$ מתאים בדיוק למקרה שבו יש לנו $n-k$ עצמים זהים והיתר שונים זה מזה (כך שהנוסחה היא בעצם $\frac{n!}{\left(n-k\right)!1!1!\cdots1!}$ ואין צורך לכתוב את ה- $1$ -ים במכנה כי $1!=1$ ). למה הסיטואציה הזו אכן מתארת חליפות? כי ניתן לחשוב על כך שאנחנו מניחים על העצמים שלנו פתקים שבהם או שכתוב מספר כלשהו מ- $1$ עד $k$ (שמתארים את מספרם בבחירה) או שכתוב עליהם "לא נבחר", וכל פתקי ה"לא נבחר" זהים זה לזה ויש $n-k$ מהם.

טוב, אז זה מסיים את עניין הבחירה בלי החזרות. הבה ונעבור לבחירה עם החזרות – שימו לב שכאן $k$ יכול להיות גדול מ- $n$ כי האיברים לא יכולים "להיגמר" לנו. הסיטואציה כאן מאוד מעניינת – מצד אחד, אם יש חשיבות לסדר הנוסחה פשוטה ביותר (כה פשוטה שאני ממליץ לכם לנסות ולהמציא אותה לבד לפני שתקראו מה שאכתוב). מצד שני, הנוסחה עבור בחירה עם החזרות אך בלי חשיבות לסדר היא קשה יחסית – כה קשה שאיני חושב שמלמדים אותה כלל בתיכון, אפילו אם כן לומדים קומבינטוריקה. למרות זאת הדגש צריך להיות על הקושי היחסי: הנוסחה אינה נוראית כלל ואני מקווה שעד סיום הפוסט יוכלו כל הקוראים לפתח אותה בעצמם.

הנוסחה לבחירה עם החזרה ועם חשיבות לסדר היא תוצאה ישירה של עקרון הכפל. תהליך הבחירה שלנו הוא בן $k$ שלבים; בכל שלב אנחנו בוחרים אחת מ- $n$ אפשרויות שונות. יש לנו אם כן בסך הכל $n\cdot n\cdots n=n^{k}$ אפשרויות שונות. קל להתבלבל ולשכוח מי במעריך החזקה ומי בבסיס (כלומר, האם זה $k^{n}$ או $n^{k}$ ) ולכן אני ממליץ לנקוט בגישה הבאה: כמה מספרים דו ספרתיים יש, אם מרשים גם לאפס להופיע (כלומר, $3$ הוא המספר ה"דו ספרתי" $03$ וכדומה)? $2^{10}$ או $10^{2}$ ? ובכן, $2^{10}=1024$ כך שברור שיש כאן בעיה; לעומת זאת $10^{2}$ מתאים בדיוק, וזה לא מפתיע כי מספר דו ספרתי מורכב מבחירה של אחת מ-10 הספרות האפשריות בתור ספרת האחדות, ואחת מ-10 הספרות האפשריות בתור ספרת העשרות.

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

הדרך הנוחה ביותר לתאר זאת היא באמצעות סיפור מעשיות. בחירה של $k$ מתוך $n$ איברים ללא חשיבות לסדר ועם החזרה ניתן לתאר בתור סידור כדורים בתאים: נניח שיש לנו שורה של $n$ תאים ממוספרים, ו- $k$ כדורים זהים. אנחנו זורקים כדורים לתוך התאים ובסוף רואים מה קיבלנו. אם בתא מס' 1 יש שני כדורים, אנחנו אומרים שבחרנו את האיבר מס' 1 בדיוק שתי פעמים; אם בתא 2 אין כדורים כלל אנו אומרים שאת איבר מס' 2 בכלל לא בחרנו, וכן הלאה.

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

בגישה הזו מה שאני "בוחר" הוא את המקומות שבהם אני רוצה לשים את המחיצות. על פניו כל רווח בין שני כדורים, או בין כדור והקיר, הוא מיקום חוקי. יש $k$ כדורים ולכן $k+1$ רווחים (ציירו שני כדורים ותראו את שלושת הרווחים: מימין לכדור הימני, משמאל לשמאלי, ובין שניהם). לכן יש לי בחירה של $n-1$ איברים מתוך קבוצה של $k+1$ איברים, בלי חשיבות לסדר ועם החזרה, כי אפשר לבחור באותו רווח כמה פעמים… היי, רגע, אז מה בעצם השגתי כאן? אני עדיין תקוע עם בעיה של בחירה עם החזרה ולא שיפרתי כלום!

אם לגלוש לרגע למתמטיקה יותר מתקדמת, כשכזה דבר קורה זה לא בהכרח סוף העולם. אפשר לחזור על אותו תהליך שוב ושוב ולראות האם זה הופך את הבעיה בהדרגה לפשוטה יותר. לרוע המזל, זה לא מה שקורה כאן – מבעיה של בחירת $k$ מתוך $n$ עברתי לבעיה של בחירת $n-1$ מתוך $k+1$ , ואם אעשה את התעלול שוב אחזור לבעיה של בחירת $k$ מתוך $n$ . צריך להוסיף עוד תעלול לתמונה, אם כך. והתעלול הזה פשוט – אני הולך לאסור על תאים ריקים.

הטענה שלי היא כזו: מספר הדרכים השונות לחלק $k$ כדורים ל- $n$ תאים (בלי חשיבות לסדר) שווה בדיוק למספר הדרכים השונות לחלק $n+k$ כדורים ל- $n$ תאים כשבסוף החלוקה אין תאים ריקים. למה? זה פשוט: כי נתחיל את החלוקה בלשים כדור אחד בכל תא. כך הבטחנו שמה שחייב להתקיים, מתקיים, ואז $k$ הכדורים שנותרו אפשר לחלק בשקט ובלי מגבלות כלשהן. אם כן, המרנו את הבעיה שלנו לבעיה אחרת, שאותה יהיה לנו קל יותר לתקוף.

נחזור לבעיית השמת המחיצות. אם אסור שיהיו תאים ריקים, זה אומר שאסור לשים שתי מחיצות בין אותו זוג כדורים, ואסור לשים מחיצה בין כדור ובין הקיר. מצד שני, יש לנו הפעם $n+k$ כדורים, ולכן יש בסך הכל $n+k-1$ רווחים שבהם ניתן לשים את $n-1$ המחיצות. הפעם הבחירה היא בלי החזרות כי כאמור, אסור לשים שתי מחיצות בין אותו זוג כדורים – אסור לבחור פעמיים באותו רווח שבין כדורים. לכן יש לנו בחירה של $n-1$ איברים מתוך $n+k-1$ איברים, וזה בדיוק ${n+k-1 \choose n-1}$ , ואת זה ניתן לכתוב גם כ- ${n+k-1 \choose k}$ . בזאת מצאנו את הנוסחה לשיטת החלוקה הרביעית והאחרונה.

לפני שנסיים להפעם אני רוצה לתאר שימוש פשוט אחד בבחירה עם החזרה ובלי חשיבות לסדר, שבינתיים אולי נראית מפחידה ומסובכת ולא מועילה כלל. נביט במשוואה $x_{1}+x_{2}+\dots+x_{n}=k$ , כאשר $k$ הוא מספר שלם והערכים שאנחנו מרשים למשתנים לקבל הם רק ערכים שלמים אי שליליים (משוואות כאלו צצות בפועל! בעולם האמיתי! תאמינו לי!). כמה פתרונות יש למשוואה הזו? בדיוק מספר האפשרויות לבחור $k$ איברים מתוך $n$ , עם החזרה ובלי חשיבות לסדר. למה? אשאיר זאת כתרגיל לקורא.

תגים: מתמטיקה תיכונית, קומבינטוריקה
שייך לקטגוריות קומבינטוריקה | 9 תגובות »