משפט קוק-לוין

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

על P=NP מעל חבורות אבליות – מבוא שלם

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

מעגלים בוליאניים – מה זה בכלל?

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

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

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

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

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