המשפט היסודי של האלגברה – הוכחה אלגברית

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

ילדים (הסתברותיים) זה שמחה

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

תורת גלואה – מה הרעיון הבסיסי בה?

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

למה (בגדול, מאוד בגדול) לא ניתן לפתור משוואות ממעלה חמישית ומעלה, ומה זה בכלל אומר?

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

למה זכרון שהוא פחות מלגלג הוא קבוע?

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

אז מה בין קודים לתיקון שגיאות והוכחת משפט ה-PCP?

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