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

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

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

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

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

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

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

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

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

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