שורש, ההוכחה (חלק א’)

אם השעה היא 19:00 ושואלים אותנו מה תהיה השעה עוד שש שעות, אנו עונים שהיא תהיה 1:00. איך אנחנו יודעים? אנחנו מחברים 6 ל-19, מקבלים 25, ומחסרים 24 מהתוצאה, כי הרי בשעון, כל 24 שעות "מתחילים מהתחלה". זו דוגמה לאריתמטיקה מודולרית – במקרה הזה, אריתמטיקה מודולו 24. המשמעות היא פשוטה: האיברים שלנו הם מספרים שלמים …

על משת”פים ונבוטים בראש, והקשר שלהם להוכחות אפס-ידע

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

מוכיחים את הלא נודע

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

עימות המוכיחים

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

מוכיח בשער

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

בסיס מוצק מי ימצא

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

לבחור או לא לבחור – זו השאלה

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