מבחן 2007 סמסטר א' מועד ב' (גריסה 1) שאלה 7

[Erez]

מהי המחלקה המינימלית ביחס להכלה אליה שייכת הבעיה הבאה:
קלט: גרף מכוון ושני צמתים x ו-y.
פלט: האם כל מסלול מx לy הוא באורך לכל היותר n/2 ?

הפתרון הוא PH.
(לא הייתה אפשרות לבחור coNP, אבל נראה לי שזה גם ב coNP ?)

אני חשבתי שהפתרון הוא בNL ע"י האלג' הבא:

נסתכל על הבעיה המשלימה:
האם קיים מסלול מx לy כך שאורכו > n/2 ?
(NL = coNL כידוע).
נתחיל בx, ננחש בכל פעם צומת מהמסלול ובסוף נבדוק שהמסלול מהאורך הרצוי.
מה ההבדל בין זה לבין שאם היה קיים מסלול אחד היינו מנחשים בדיוק אותו ?

[itai rosenblatt]

גם אנחנו התלבטנו על השאלה...
אבל שים לב שכתוב כל מסלול פשוט
האלגוריתם לא מבטיח לך מסלול פשוט

2010/6/23 Erez <erezh...@gmail.com>