הבעיה העשירית של הילברט – הפונקציה האקספוננציאלית היא דיופנטית

סוף סוף הגענו אל האקשן האמיתי. כזכור, עבור $latex a>1$ הגדרנו את משוואת פל $latex x^{2}-dy^{2}=1$ כאשר $latex d=a^{2}-1$, וסימנו בתור $latex x_{n}\left(a\right)$ את סדרת ערכי ה-$latex x$-ים של פתרונות של המשוואה (כשכולם מוצגים בתור "חזקות" של הפתרון היסודי). המטרה … להמשיך לקרוא

הבעיה העשירית של הילברט – איך משוואת פל קשורה לכל העניין?

בואו נחזור לדבר על הבעיה העשירית של הילברט שעזבתי בשיא המתח – בדיוק לפני החלק הטכני ביותר, שנתחיל לטפל בו הפעם. תזכורת קטנה למי שאין לו כוח לקרוא את הפוסטים הקודמים: המטרה שלנו היא להוכיח שהפונקציה $latex f\left(n,k\right)=n^{k}$ – "הפונקציה … להמשיך לקרוא

דטרמיננטות

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

פונקציות יוצרות – והפעם ברצינות (חלק ב')

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

IP=PSPACE – ההוכחה (חלק ב')

בפוסט הקודם שעסק בהוכחה ש-$latex \mbox{IP}=\mbox{PSPACE}$ הראיתי מערכת הוכחה אינטראקטיבית עבור השפה $latex \overline{3\mbox{SAT}}$. זו הייתה הדוגמה הראשונה למערכת הוכחה "רצינית", כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה … להמשיך לקרוא

IP=PSPACE – ההוכחה (חלק א')

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

היה זה תענוג לגזור

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

משפט לדנר, או – מפרקים לגורמים את NP

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

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

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

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

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

איך מוצאים את נוסחת פיבונאצ'י?

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

המתמטיקה של RSA

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