בוחן 2007 סמסטר א מועד 2
Eugene
קלט: גרף מכוון G עם n צמתים.
שאלה: האם קיימים בגרף שני צמתים x,y כך שהמסלול הפשוט הקצר ביותר בין x
ל-y הוא באורך לפחות n/2 .
(נניח שכל המחלקות הבאות הן שונות זו מזו).
א. L
ב. NL
ג. P
ד. NP
ה. PSPACE
התשובה היא ב' ולא ברור למה. הרי אמרנו שמסלול פשוט אנחנו לא יכולים
לוודא במקום לוג'?!
Omer Eyal
אם אתה מגיע ל Y בדרך אתה מחזיר לא, אחרת כן
Omer Eyal
לכאורה אפשר לפתור ככה מסלול המילטון
לא ברור
ptyl eyal
כנראה בגלל שזה מסלול פשוט.
מסלול ייקרא פשוט אם הוא אינו עובר באף צומת יותר מפעם אחת.
אז צריך לבדוק שאנחנו לא עוברים באף צומת יותר מפעם אחת. ואת זה לא ניתן
לעשות במקום לוגריתמי כי צריך לשמור את כולם.
Eugene
On Aug 9, 11:30 am, ptyl eyal <the.p...@gmail.com> wrote:
> לא יודע, אבל אם הגעת במסלול לא פשוט לקודקוד ב n/2 צעדים, אז לבטח יש מסלול
> פשוט שיביא אותך לשם ב n/2 צעדים כי אפשר להסיר את המעגלים ולהגיע לשם בפחות
> צעדים, לא?
>
> 2009/8/9 Anna <annis...@gmail.com>
Miriam
כלומר NP
אתה צריך עד שהמסלול הארוך יותר הוא באורך לפחות
n/2
אז אם יש מסלול באורך הזה לפחות, קח אותו בתור עדות
אי אפשר לפתור את זה איכשהו בזמן פולינומיאלי?
BFS?
לא יעבוד...? =\
Eugene
ptyl eyal
arisha84
On 9 אוגוסט, 11:59, ptyl eyal <the.p...@gmail.com> wrote:
> השאלות האמריקאיות האלה זה פשוט זוועת עולם
>
> 2009/8/9 Eugene <princeeug...@gmail.com>
Miriam Po
Eugene
Miriam Po
Eugene
יש עוד אנשים שרואים שהתשובה היא ב' ולא ד'.
Eugene
"הארוך" מופיע מילה "הקצר" וזה משנה את כל המצב.
Ishay Haviv
The complement of the question in this problem (Q6 in the quiz) is:
for every two vertices x,y the shortest simple path from x to y is of
length smaller than n/2. This can be decided easily in NL - go over
all the pairs x,y and guess a path from x to y of length smaller than
n/2 and verify it. Notice that we cannot verify that the guessed path
is simple but it's not important, since there is a (general) path of
length at most k from x to y iff there is a *simple* path of length at
most k from x to y (why?). In order to be sure that the answer is NL
(and not L) you also have to show that the problem is NL-hard.
Notice that if we are interested in a *simple* path of length *at
least* k we don't know how to do it in NL since we cannot verify that
the path is simple (and for such questions you can usually show
NP-hardness by a reduction from Hamilton Path).
Ishay
Quoting arisha84 <aris...@gmail.com>:
>> > > > > > > > > ל-y הוא באורך לפחות n/2 .
>> > > > > > > > > (נניח שכל המחלקות הבאות הן שונות זו מזו).
>>
>> > > > > > > > > א. L
>> > > > > > > > > ב. NL
>> > > > > > > > > ג. P
>> > > > > > > > > ד. NP
>> > > > > > > > > ה. PSPACE
>>
>> > > > > > > > > התשובה היא ב' ולא ברור למה. הרי אמרנו שמסלול פשוט אנחנו לא
>> > יכולים
>> > > > > > > > > לוודא במקום לוג'?!
> --~--~---------~--~----~------------~-------~--~----
~> קיבלת הודעה זו כיוון שנרשמת ל קבוצת "Complexity Course, Spring 2009,
> Tel Aviv University" בקבוצות Google.
> כדי לפרסם בקבוצה זו, שלח דוא"ל אל
> complexity-course-spring...@googlegroups.com
> לביטול המנוי בקבוצה זו, שלח דוא"ל ל
> complexity-course-spring-2009-...@googlegroups.com
> לאפשרויות נוספות, בקר בקבוצה זו
> בhttp://groups.google.com/group/complexity-course-spring-2009-tel-aviv-university?hl=iw
> -~----------~----~----~----~------~----~------~--~---
>
>