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

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

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

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

חידת קופסאות

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

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

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

נגזרת – בשביל מה זה טוב? (בעיות קיצון, חלק ב')

בפוסט הקודם עסקנו בשתי בעיות "מציאותיות" ובסופו של דבר בנינו מודל מתמטי עבורן שבא לידי ביטוי בפונקציה ממשית מסויימת. זה מעביר אותנו לבעיה הכללית הבאה: נתונה פונקציה ממשית $latex f\left(x\right)$, ואנו רוצים למצוא ערכי $latex x$ שעבורם $latex f\left(x\right)$ היא מקסימלית או מינימלית. הנחת היסוד שלנו הוא ש-$latex f\left(x\right)$ היא פונקציה "נחמדה" – ניתן לגזור …

נגזרת – בשביל מה זה טוב? (בעיות קיצון, חלק א')

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

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

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

המשפט היסודי של החשבון הדיפרנציאלי והאינטגרלי

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

לוגיקומיקס

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