יומיות 22.01.2020: מה המשמעות של ההוכחה החדשה שכולם מדברים עליה, MIP*=RE?

סחבק בחופש של שלושה ימים. התוצאה? פוסט יומיות ע-נק!

1. מאמר חדש, 165 עמודים אורכו, מוכיח ש-MIP*=RE. יש גם קישור ל"בעיית העצירה" המיתולוגית ממדעי המחשב, אבל אני בכוונה לא מתייחס אליה. הרי הנוסחא מכילה מספיק אותיות מוזרות ויש גבול לכמה דברים אפשר להסביר באייטם קצר אחד.

לפני ההסבר, קישורים!

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

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

עכשיו לגבי התוצאה.

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

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

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

בואו נפרק את המושג לגורמים.

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

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

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

הדבר האחרון שמוסיפים הוא הכוכבית: *MIP. מה המשמעות של הכוכבית? המשמעות היא שה-provers הם מחשבים קוונטים שקשורים אחד לשני. כי בתורת הקוונטים שני דברים שונים במקומות פיזיים שונים עדיין תלויים אחד בשני.

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

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

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

2. וואו, כזה משחק לוח אני רוצה! מונופול חבורת הזבל! בואו נראה מי מהקוראים מכיר את חבורת הזבל.

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

חוקר האבטחה ברוס שנייר בפוסט מפורט על אבטחת 5G.

הוא מונה בעיות בשתי קטגוריות.

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

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

4. סטפן טילטו מקוטאקו שיחק ב-87 משחקים ב-2019, ובשנה ה-14 ברציפות הוא מעלה את כתבת סיכום שנת משחקי המחשב שלו.

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

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

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

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

אישית? אני אגיד שאני מאמין כשאני אראה את זה.

8. יוטיוב היא אוצר בלום של סרטי אנימציה ישנים, הנה איך להתחיל למצוא אותם.

9. כתבה ארוכה ומופלאה על pixel art ועל אמנות באופן כללי. קריאה נהדרת ומחכימה לכל מי שרוצה לשמוע מחשבות חכמות על אמנות דיגיטלית.

10. התערוכות הכי טובות של 2019, פוסט בעברית.

11. הצעצועים הכי טובים של 2019, תמיד כיף לראות.

12. מיטב האנימציה ברשת בשנת 2019, עוד פוסט בעברית.