approximation factor

[Asaf]

שאלה מ 2007, סמסטר א, מועד א.

4. נתייחס לפקטור קרוב כגדול מ-1 עבור בעיות מינימיזציה וקטן מאחד עבור
בעיות מקסימיזציה.
אם ידוע שבעיית אופטימיזציה A היא NP-קשה לקרוב לכל פקטור טוב יותר מ-c
אז:
א. אם A בעיית מקסימיזציה אז לכל a בין 1 ל 0 מתקיים כי בעיית Gap-A
[2ca, a] היא NP קשה
ב. אם A בעיית מינימיזציה אז לכל a בין 1 ל 0 מתקיים כי בעיית Gap-A[2a/
c, a] היא NP קשה
ג. א + ב
ד. אף אחד מהנ"ל.

לפי הפתרונות התשובה היא ד.

מישהו יכול להסביר?

תודה,

אסף.

[Yossi]

שים לב שרק אם ידוע ש*כן* קיים קירוב C, אז בעיות ה GAP האלה הן לא קשות.
זה שלא קיים קירוב C לא בהכרח גורר את זה שהן כן קשות.

דוגמא היא שאי אפשר לקרב את 3SAT עבור קבוע 7\8, אבל GAP3-SAT
[0.2,0.2001] היא קלה, היא תמיד אמת.