מבחן 2002, א א, שאלות 4,5

[kiri...@gmail.com]

(4)נתונה הבעיה הבאה:
קלט: נוסחת E2CNF , ומספר טבעי k.
שאלה: האם קיימת השמה שמספקת את הנוסחה כך שלכל היותר k משתנים מקבלים
ערך T?
מהי המחלקה הקטנה ביותר שאליה שייכת הבעיה, אם כל הליטרלים הם משתנים
(ולא שלילות של משתנים)?
א.PSPACE
ב.NPC
ג.NP
ד.coNP
ה.P

התשובה הנכונה: ב.

(5) כנ"ל, כאשר בכל הסגר, ליטרל אחד הוא משתנה והשני הוא שלילה של משתנה.
א.PSPACE
ב.NPC
ג.NP
ד.coNP
ה.P

התשובה הנכונה: ה.

האם ניתן לקבל הסבר? אין לי אפילו קצה חוט.

תודה מראש

[arisha84]

(5)
ניתן לקחת את ההשמה F לכל המשתנים, וזה תמיד יספק את הנוסחה
לכן הבעיה טריוויאלית

[eviatark]

תחשוב איך רדוקציה מ vertex cover פותרת לך את הבעיה.

On 8 אוגוסט, 12:54, "kirils...@gmail.com" <kirils...@gmail.com> wrote:

[Eugene]

לגבי 4 אני לא מסכים שזה שלילה של בדיוק אותו משתנה. זה יכול להיות כל
משתנה אחר ולכן הצבה טריוויאלית לא בהכרח תעבוד.
אני חשבתי יותר בכיוון לבנות גרף בדומה למה שראינו בתרגול 5 בתאריך
21.5.09 ולהריץ אלגוריתם מציאת מסלול.

[Asaf]

גם אם לא מדובר על שלילה של אותו המשתנה עדיין בכל פסוקית יש שלילה של
משתנה כלשהו, לכן אם כל המשתנים יקבלו ערך F, אזי בכל פסוקית יהיה המשתנה
הרגיל (לא שלילה של משתנה כלשהו) שיקבל ערך F, ויהיה המשתנה השני שיקבל
ערך T,
לכן הפסוקית תסתפק למרות שכל המשתנים קיבלו ערך F,
כלומר לכל K טבעי התשובה תמיד כן ולכן הבעיה כן טריוויאלית.

> > > תודה מראש-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-

[arisha84]

ההשמה שאתה מציב היא F לכל המשתנים.
מכיוון שלפי הנתון בכל פסוקית יש משתנה ושלילה של משתנה (לא חייב להיות
אותו משתנה)
כל הפסוקיות יסופקו.
כלומר לא משנה מהו K
תמיד אפשר לספק כאשר אין אף משתנה שמקבל ערך T
כלומר הבעיה טריוויאלית

On 8 אוגוסט, 16:05, Eugene <princeeug...@gmail.com> wrote:

[odedr]

In Q4, use an easy reduction from VC (the problem is essentially
equivalent, just in a different language)
In Q5, the problem is indeed trivial since the all FALSE assignment
always satisfies it.

-- Oded