2006 b - moed b

[HAIM KRASNIKER]

שאלה 8,

כמה מהבעיות הבאות הן NP קשות?

מדוע התשובה היא 4?

הבעיה השנייה לא אמורה להיות ב P? פשוט נחזיר תמיד כן כי לכל נוסחת E3SAT יש תמיד השמה שמספקת 7/8 מההסגרים..

ולכן התשובה צריכה להיות 3?

.או שלא ההבנתי את הגדרת הבעיה ואשמח אם מישהו יסביר לי.

תודה,חיים.

[odedr]

Shalom Haim,

Indeed there's something apparently wrong with the solution file
(unless
I'm missing something).

Out of the four problems listed there, only *2* are NP-hard
(those with gap 9/2006,10/2006 cannot be NP-hard since
the answer to them is always YES)

-- Oded

[Yossi]

באותו מבחן, שאלה 4:

4. נניח ש- P שונה מ-NP,
ו-A ו-B בעיות מינימיזציה,
A<(p)B
וגם יש אלגוריתם c-קרוב פולינומיאלי ל-B
(c קבוע).
אז בהכרח
א. יש אלגוריתם קרוב פולינומיאלי ל-A שמבטיח יחס קרוב c.
ב. יש אלגוריתם קרוב פולינומיאלי ל-A שמבטיח יחס קרוב קבוע, אבל לא בהכרח
c.
ג. A היא בעיה NP קשה.
ד. אף אחד מהנ"ל.

התשובה היא ד', אבל לא הצלחתי להוכיח למה.

On 1 יולי, 22:31, odedr <ode...@gmail.com> wrote:
> Shalom Haim,
>
> Indeed there's something apparently wrong with the solution file
> (unless
> I'm missing something).
>
> Out of the four problems listed there, only *2* are NP-hard

> (those with gap 9/2006,10/2006cannot be NP-hard since

[Ido Ben Eliezer]

A לא בהכרח NP - קשה -- למעשה אין שוב סיבה מהנתון שהיא תהיה.

גם העובדה שמובטח קירוב ל- B לא מבטיח קירוב קבוע ל - A (הכי קל לראות את זה מהדוגמאות שאנו ראינו של VC ו - IS, למרות שמקרה זה לא מתאים לגמרי כי אחת היא הבעיות היא בעיית מקסימיזציה, אבל בעזרת שינוי לא קשה אפשר לקבל דוגמה מתאימה).

2009/7/2 Yossi <joza...@gmail.com>