קטגוריה: תורת הסיבוכיות

מדעי המחשב ומדוע הם מגניבים

פוסטים:

• Jan 24, 2020

  מה זה אומר ש-MIP*=RE? (חלק ב': מה זה אומר MIP*?)

• Jan 23, 2020

  מה זה אומר ש-MIP*=RE? (חלק א': מה זה אומר RE?)

• Nov 7, 2018

  ”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה כן (אזהרה - עלול לכלול מתמטיקה)

• Oct 23, 2018

  ”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה לא (וקצת מה כן)

• Sep 4, 2017

  על הבעיה הקשה של מלכות השחמט והבעיה הקשה עוד יותר של מלקות התקשורת

• Jul 12, 2016

  ההוכחה הארוכה ביותר בהיסטוריה! (או: איך פותרי SAT מתגברים על בעיות קומבינטוריות, אבל היי זה שם פחות מפוצץ)

• Jul 23, 2015

  משפט קוק-לוין

• May 28, 2015

  משפט קלייני - הוכחה נוספת

• May 14, 2015

  למת הניפוח לשפות רגולריות - גרסה מלאה

• May 7, 2015

  משפט מייהיל-נרוד - נקודת מבט נוספת, ואלגוריתמי מינימיזציה

• Apr 29, 2015

  בעיות הכרעה עבור שפות פורמליות

• Apr 26, 2015

  שפות חסרות הקשר - תכונות סגור

• Apr 15, 2015

  שפות חסרות הקשר - למת הניפוח, הלמה של אוגדן ושפות רב משמעיות

• Mar 31, 2015

  שקילות אוטומט מחסנית ודקדוק חסר הקשר

• Mar 22, 2015

  אוטומט מחסנית

• Mar 15, 2015

  אז מה הקשר בין דקדוקים חסרי הקשר ופונקציות יוצרות?

• Mar 5, 2015

  מבוא לדקדוקים חסרי הקשר

• Feb 11, 2015

  משפט מייהיל-נרוד

• Feb 3, 2015

  למת הניפוח לשפות רגולריות

• Jan 29, 2015

  ביטויים רגולריים

• Dec 24, 2014

  שפות רגולריות - משפט קלייני

• Dec 21, 2014

  שפות רגולריות - תכונות סגור (חלק ב')

• Dec 15, 2014

  שפות רגולריות - תכונות סגור (חלק א')

• Nov 19, 2014

  אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

• Nov 11, 2014

  אוטומטים ושפות רגולריות - מבוא

• Dec 11, 2013

  פותרים את SAT - אלגוריתם DPLL

• Nov 24, 2013

  פותרים את SAT: המקרים של HORNSAT ו-2SAT

• Nov 14, 2013

  רזולוציה - איך אפשר להוכיח שאי אפשר?

• Nov 11, 2013

  מה זו בעיית SAT ולמה חשוב לפתור אותה?

• Jun 30, 2013

  על P=NP מעל חבורות אבליות - סוף דבר

• Jun 15, 2013

  על P=NP מעל חבורות אבליות - מבוא שלם

• May 11, 2012

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

• May 14, 2011

  IP=PSPACE - ההוכחה (חלק ב')

• May 7, 2011

  IP=PSPACE - ההוכחה (חלק א')

• Apr 4, 2011

  אז מהי PSPACE?

• Mar 25, 2011

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

• Mar 17, 2011

  אז מה זה IP=PSPACE?

• Mar 5, 2011

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

• Mar 1, 2011

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

• Jan 24, 2011

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

• Jan 23, 2011

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

• Jan 18, 2011

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

• Jan 9, 2011

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

• Nov 10, 2010

  משפט לדנר, או - מפרקים לגורמים את NP

• Aug 31, 2010

  כיצד אורקלים מנבאים שקשה להוכיח ש-P שונה מ-NP

• Aug 16, 2010

  אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

• Aug 15, 2010

  אז מה זה עניין P=NP, בעצם?

• Aug 10, 2010

  הוכחה ש-P שונה מ-NP?

• Oct 4, 2009

  למה זכרון שהוא פחות מלגלג הוא קבוע?

• Oct 1, 2009

  אז מה בין קודים לתיקון שגיאות והוכחת משפט ה-PCP?

• Sep 23, 2009

  קודים לתיקון שגיאות (שניתנים לבדיקה מקומית)

• Sep 19, 2009

  משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הסתברותית

• Aug 30, 2009

  אוטומטים סופיים ושפות רגולריות

• Aug 18, 2009

  דיון מקרי על אלגוריתמים הסתברותיים

• Jul 22, 2009

  למה RSA טרם נפרץ? (בגלל החשיבה המתמטית הלא פרקטית)

• Jan 7, 2008

  על בעיות שהן בכלל תסבוכת שלמה

• Dec 23, 2007

  אז מה זה בעצם אי דטרמיניזם? קשה להחליט

• Dec 16, 2007

  על הבעיה המסובכת של מציאת מחט בערימת שחת

• Dec 11, 2007

  מכונת טיורינג, 2: הנקמה (המסובכת)

• Dec 5, 2007

  למה גם מה שפתיר לא פתיר (זה מסובך)

• Nov 10, 2007

  אוף, כל הקטע עם השורש הריבועי באמת יוצא מסובך

• Nov 5, 2007

  ועכשיו למשהו מסובך יותר - הוצאת שורש ריבועי!

• Sep 7, 2007

  המגדל הלוהט

• Jul 25, 2007

  על משת”פים ונבוטים בראש, והקשר שלהם להוכחות אפס-ידע

• Jul 17, 2007

  עימות המוכיחים

• Jul 10, 2007

  מוכיח בשער