Announcements

Handout and previous exams
The following handout will be distributed along with the exam. Links to previous exams have been added to the "Previous exams" tab (on the left).
published on 29/01/2017 00:15:58 by Eden Chlamtac
תיקון קטן בניסוח ההוכחה שראינו בכיתה
בהוכחה שראינו לכך שקיימת שפה B שעבורה PB≠NPB לא דייקתי בניסוח בצעד האינדוקטיבי בבניית B.

אמרנו שכאשר המכונה Mi+1 מבצעת שאילתא עבור מחרוזת x ששייכת ל- K1 U … U Ki, היא תקבל תשובה בהתאם להחלטה שכבר קיבלנו בעבר (לגבי שייכות x ל-B).

בהמשך התיאור, כתבתי שאם המכונה Mi+1 מבצעת שאילתא ל-x כך שלא ביצענו בצעדים קודמים שאילתות ל-x, אזי נחליט ש-x לא שייכת ל-B. ניסוח זה לא מדוייק. התנאי הנכון צריך להיות אם המכונה מבצעת שאילתא ל-x כך ש״x לא שייכת ל- K1 U … U Ki" (אזי נחליט ש-x לא שייכת ל-B).

published on 29/12/2016 10:21:00 by Eden Chlamtac