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

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

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

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

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

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

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

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

מוכיח בשער

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

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

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

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

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