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

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

אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

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

אז מה זה עניין P=NP, בעצם?

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

דיון שאינו חסר תוחלת במשתנים מקריים

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

הוכחה ש-P שונה מ-NP?

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

בהינתן שאנחנו יודעים הסתברות בסיסית, כמה קל להבין הסתברות מותנית?

בפוסט הקודם התחלתי לדבר על הסתברות בסיסית והצגתי כמה רעיונות בסיסיים. אמרתי שאנחנו ממדלים סיטואציה הסתברותית עם מרחב הסתברות שכולל קבוצה $latex X$ (מרחב המדגם) של כל התוצאות האפשריות של הסיטואציה ההסתברותית, כך שלכל $latex a\in X$ (לכל תוצאה $latex … להמשיך לקרוא