המשחק נים

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

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

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

אז מה זה IP=PSPACE?

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

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

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

מה זו סיבוכיות תקשורת?

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