חישוביות 2024 תרגיל 4 שאלה 1 - הגדרת שפה שלימה לפי רדוקצית קוק, הגדרת גרסה לא דטרמיניסטית של קארפ
Вставка
- Опубліковано 14 жов 2024
- ההוכחה שקיימת שפה NP שלימה עבור סעיף א:
• הרצאה 3 - קיימת שפה NP...
ההוכחה שכל רמה בהיררכיייה הפולינומית סגורה לרדוקציית קארפ עבור סעיף ב:
• הרצאה 7 - כל רמה בהירר...
💯💪💪
היי יונדב, תודה רבה!!
יש לך תשובה לגבי מה שהיא שאלה אותך בסרטון לגבי סעיף ב, כלומר אם לא כל תשובה שמוחזרת נכונה אז מה התשובה הייתה?
בכיף!
זהו אז צריך להבין על מה אנחנו מדברים אם אנחנו רוצים לדבר על רדוקצייה לא דטרמיניסטית. רדוקציית מיפוי בסופו של דבר זה אלגוריתם שפותר בעיית חיפוש, ולכן בד"כ כשמגדירים חוסר דטרמיניזם בבעיות חיפוש, מדברים על כך שהאלגוריתם מחזיר תמיד תשובה נכונה, או שהוא מחזיר סימן של "לא יודע"
אם נדבר על רדוקצייה לד מסגנון כזה, אז נוכל להפעיל אותה מתוך מכונת "אן פי" ולדחות דיפולטיבית כאשר החוזר "לא יודע", ואם הוחזר פלט "אמיתי, לפתור אותו עם המכונה המכריעה את הרמה הרלוונטיות בהיררכייה.
היי רציתי לשאול לגבי סעיף ב׳, מצד אחד ברור לי שאם קיימת s בעיה phשלמה אז היא שייכת לרמה kכלשהי וכל בעיות ברמות מעליה שייכות לרמה שלה כי יש רדוקציית קארפ מהן לבעיה , ואז ההיררכיה קורסת לרמה הk.
מצד שני מה מונע ממני ממני לנסות לחקות את סעיף א׳ ולהגדיר בעיה s שמקבלת את כל כך ש: m היא מ״ט וקיים k טבעי כלשהו כך שקיים y1 שלכל y2 קייםy3..... עד yk ,שהרצת המכונה m על x עם k העדויות לt צעדים מחזירה 1, ובאותו אופן שהוכחנו את סעיף א׳ להוכיח את שs הזו היא ph שלמה? תודה!
אתה מתכוון לשאול שאז ההיררכייה לא באמת תקרוס לרמה ה "קיי"?
כי להראות שפה שהיא "סיגמא קיי ועוד אחד" שלימה לא אומר שההיררכייה לא קורסת לרמה ה קיי.
כמו שבעצם זה שאנחנו מראים שקיימת שפה שהיא "אן פי שלימה" לא הראינו ש "אן פי" שונה מ "פי".
אתה אכן יכול להראות שלכל רמה בהיררכייה הפולינומית קיימת שפה שהיא "שלימה" עבור הרמה הזו
אני מתכוון שאני אגדיר את s (הקבוצה שמסמלצת את הריצה של m על x עם העדויות) לא עבור k ספציפי אלה שאני רק אדרוש שיהיה k טבעי כלשהו שבעזרת k עדויות m תכריע את x. בעצם בהגדרת s אני לא מגביל למספר עדויות ספציפי אלא רק דורש שיהיה קיים k טבעי כזה.
ובאמת לכל בעיה אחרת s' בph קיים k כלשהו שבעזרת k עדויות אני יכול לוודא אותה.
אבל אולי לפי ההגדרה שאני חושב עליה s לא שייכת לph
אוקיי הבנתי לאן אתה חותר@@alonlivne8429
אז לדעתי הדרך להגדיר מה שאתה חותר אליו זה שה"קיי" יהיה חלק מהמילה, ז.א מילה בשפה תכיל גם את מספר הכמתים שאנחנו מדברים עליו. שפה כזו נוכל להראות שהיא "היררכיה פולינומית-קשה", אבל כפי שאתה אומר, לא נצליח להראות שהיא בתוך רמה כלשהי בהיררכייה.
@@alonlivne8429
למעשה שפה כזו תהיה "פיספייס שלימה", בהיותה דומה לשפת ה"נוסחאות הבוליאניות המכומתות":
en.wikipedia.org/wiki/True_quantified_Boolean_formula