שאלות לאורקלים למינהם...
arisha84
[7/8, 1] היא קלה כמובן. אבל בנוסחת 3SAT כללית יכול להיות מצב שאפשר
לספק רק חצי מהפסוקיות. ואם לא איזה בעיית gap-3sat היא כן קלה בוודאות?
2. שאלה מאחד המבחנים: האם לכל C ולכל D שמקיימים 1>C<D>אפס הבעיה
gap-2sat[C,D] היא ב P? התשובה היא לא. למה?
3. ובהמשך לזה- האם בהינתן 2CNF אנחנו יודעים למצוא לה השמה מקסימלית?
איך?
-- בנוסף יש כאן שתי שאלות ממבחן, התשובה הראשונה היא NPC והשניה P. לא
ברור לי למה.
4. נתונה הבעיה הבאה:
קלט: נוסחת Exactly-2-CNF (כלומר כל הסגר ב- מכיל 2 ליטרלים של
משתנים שונים) ומספר טבעי k.
שאלה: האם קיימת השמה שמספקת את , כך שלכל היותר k משתנים מקבלים ערך
T ?
מהי המחלקה הקטנה ביותר שאליה שייכת הבעיה, אם כל הליטרלים הם משתנים
(ולא שלילות של משתנים)?
א. PSPACE
ב. NPC
ג. NP
ד. co-NP
ה. P
5. כנ"ל, כאשר בכל הסגר, ליטרל אחד הוא משתנה והשני הוא שלילה של משתנה.
א. PSPACE
ב. NPC
ג. NP
ד. co-NP
ה. P
Yossi
כלשהם. הסקנו שאי אפשר לקרב ביחס של 55\56 - אפסילון.
3. אפשר למצוא ל CNF השמה מקסימלית, הראינו בתרגול ש 2SAT-משלים היא CONL-
שלמה, אז בעצם היא ב NL.
Yossi
למצוא הצבה של כמה שפחות משתנים כך שכל הפסוקיות מסתפקות, כלומר בכל קשת
יש לפחות קודקוד אחד ב- VC.
Noam Schachter
לגבי 2SAT - לבדוק האם ספיקה / לא ספיקה זה ב-NL.
לבדוק את המספר המקסימלי של פסוקיות שניתן לספק / אחוז הפסוקיות שניתן
לספק זה כבר NPC,
למשל בגלל רדוקציה אפשרית ל-VC כמו שנאמר כאן.
בגלל זה בעיית ה-GAP-2SAT הופכת להיות קשה כאשר החסם העליון אינו 1.
לגבי 4 ו-5, 4 קשה כמו שאמרו כאן.
ב-5, ברגע שנותנים השמה -F למשתנה, נקבעים המון משתנים אחרים בשרשרת
(בגלל המבנה המיוחד של חיוב ושלילה)
לכן חופש הפעולה קטן הרבה יותר וזה ב-P.
On 1 יולי, 15:55, arisha84 <arish...@gmail.com> wrote:
odedr
It seems only (1) is left unanswered, so let me answer it:
It is actually a very good question (where did you take it from?).
Indeed, a random assignment no longer works, since it
in general satisfies less than 7/8 of the clauses.
In 1997, Uri Zwick (from our school) and Karloff (from Georgia Tech)
gave a poly-time algorithm that given a satisfiable 3CNF formula,
outputs an assignment satisfying 7/8 of the clauses:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1351
So the bottom line is that the problem is in P because
we have a poly-time algorithm that can distinguish between
the case of satisfiable 3CNF formulas, and those with <7/8
of the clauses satisfiable.
-- Oded
נעמה
התשובות לסעיפים 3,5 לא כל כך ברורות, תוכל בכל זאת לחדד?
לגבי סעיף 3, ידוע שניתן להכריע אם קיימת השמה שמספקת את כל הפסוק, אבל
למה זה אומר שאפשר גם בקלות למצוא השמה שמספקת מספר מירבי של פסוקיות גם
כשהפסוק כולו אינו ספיק?
לגבי 5, התשובה שניתנה כאן לא מוכיחה כלום.
תודה.
נעמה
נעמה
אז אני אוסיף בעצמי את מה שביקשתי, אם מישהו עוד מתעניין באחת הסוגיות -
לגבי שאלה 3, כמו שחששתי התשובה לא נכונה, יש רדוקציה מ 3SAT לבעיית
MAX-2SAT, והבעיה באמת לא קלה.
לגבי 5, אפשר פשוט לתת לכל המשתנים F. בכל פסוקית יש ליטרל אחד שמופיע כ
not ולכן היא מסופקת. לכן לא משנה מהו k, התשובה היא שניתן לספק באמצעות
השמה כנ"ל.
לילה טוב ובהצלחה לכולם.