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

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

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

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

חידת קופסאות

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

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

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

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

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

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

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

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

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

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

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

לוגיקומיקס

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