משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

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

מערכות הוכחה אינטראקטיביות – דוגמאות

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

אז מה זה IP=PSPACE?

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

NL=coNL ("משפט אימרמן") – מי, מה, כמה ולמה

בשעה טובה אנו עוברים לתיאור התוצאה השניה ב"תוצאות מפתיעות בסיבוכיות" – הטענה $latex \mbox{NL=coNL}$, או בשמה הקליט יותר, משפט אימרמן-סזלפסני (Immerman–Szelepcsényi – אין לי מושג איך לתעתק נכון), ומכאן ואילך – משפט אימרמן. אז על מה מדובר בכלל? ראשית כל … להמשיך לקרוא

משפט ברינגטון – ההוכחה

בפוסטים הקודמים הסברתי מה אומר משפט ברינגטון, וכעת אפשר להגיע לחלק היפה ביותר בכל העניין – ההוכחה שלו. האתגר הוא להראות שכל פונקציה שנמצאת ב-$latex \mbox{NC}^{1}$, כלומר ניתנת לחישוב על ידי מעגל בוליאני מגודל פולינומי ועומק לוגריתמי, ניתנת לחישוב על … להמשיך לקרוא

תוכניות מתפצלות ומשפט ברינגטון

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

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

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

פרוייקט "תוצאות מפתיעות בסיבוכיות" יוצא לדרך!

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