שתי שאלות מבחינת 2009a-a

[eviatark]

2. מהי המחלקה הקטנה ביותר ביחס להכלה שאליה שייכת בודאות הבעיה הבאה:
בהינתן גרף עם n צמתים, האם יש בו קבוצה ב"ת בגודל לפחות n-10?

א. L
ב. NL
ג. NP
ד.PSPACE
ה. coNP

התשובה הנכונה היא א'. הדרך היחידה שאני רואה לפתור זאת היא ע"י מציאת
הגרף "המשלים" ואז למצוא קליק בגודל לכל היותר 10. מציאת הקליק יכולה
להתבצע במקום לוגריתמי אולם איני רואה דרך, במקום לוגריתמי, למצוא את
הגרף המשלים, משום שאני צריך לשמור אותו בזיכרון. כלומר אני כבר לא עובד
עם הגרף שקיבלתי בקלט אלא צריך לשמור בזיכרון גרף חדש שאני יצרתי.
האם אני טועה או דרך הפתרון אינה נכונה?

7. מה מהבאים בהכרח נכון, במידה וקיימת שפה L ב- BPP שאין לה מ"ט
דטרמינסטית פולינומית שמכריעה אותה?

א. לא ייתכן, היות ו- P=BPP.
ב. P≠NP
ג. P≠PSPACE
ד. Space(n4) = Space(n10)
ה. ב'+ג' נכונות.
ו. ב'+ד' נכונות.

התשובה הנכונה היא ה'. נכונות ג' ברורה לי, אולם לא ברור לי מדוע P!= NP

תודה רבה

 

[arisha84]

2.
אני חושב שאתה לא חייב ליצור את כל הגרף בפעם אחת ולשמור בזכרון
אלא ליצור בכל פעם מקומית את החלק שאתה צריך

7.
נניח בשלילה ש
p = np
ונקבל קריסה של ההיררכיה הפולינומיאלית , כלומר
P = SIGMA2P
ומכאן
P= BPP
סתירה.

[arisha84]

גם לי יש שאלה מאותו מבחן
למה הבעיה הבאה ב
NL:
בהינתן גרף האם קיימת חלוקה של הגרף לשני קליקים

[kiri...@gmail.com]

כי ניתן לשאול על הגרף המשלים - האם יש בו שני IS, וזו בעצם השאלה האם
הגרף הוא דו-צדדי, כלומר הבעיה ב-NL

[daniel...@gmail.com]

לגבי שאלה 2:

אני חשוב שאפשר להתייחס לשאלה כאל:
האם ישנם 10 קודקודים שאם תסיר אותם מהגרף, תקבל גרף ללא קשתות.
ומכאן זה יותר פשוט להוכיח שזה ב L.

נראה לי....

[odedr]

Daniel is right. The question is equivalent to asking if there is a
vertex cover of size <= 10. And this is easy to do in logarithmic
space by trying all O(n^10) options and for each one testing whether
all edges touch the set.

-- Oded

On 7 אוגוסט, 20:57, "daniel.kle...@gmail.com"

[arisha84]

הדרך השניה לא נכונה?
אי אפשר ליצור את הגרף המשלים?