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

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

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

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

אז מה זה IP=PSPACE?

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

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

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

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

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

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

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

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

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

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

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