cc09b-b.pdf שאלה 5

2 views
Skip to first unread message

Eugene

unread,
Jun 23, 2010, 10:28:24 AM6/23/10
to Computational Complexity, Spring 2010
מישהו יודע איך פותרים את השאלה?

איזה מבין המחלקות הבאות בהכרח שווה למחלקה EXP?
א. NP^NP
ב. NP^EXP
ג. EXP^NP
ד. EXP^EXP
ה.יותר מתשובה אחת נכונה
ו. אף תשובה אינה נכונה

Einat Kreiczer

unread,
Jun 23, 2010, 10:41:59 AM6/23/10
to computational-comp...@googlegroups.com
הוא ענה על זה אתמול בתרגול חזרה, התשובה הנכונה היא ב'.
השיטה שאיתה פסלו את תשובה ד' היא בעזרת בעיה שלא למדנו בסמסטר הנוכחי ולכן לא צריכים לדעת.

בתאריך 23 ביוני 2010 17:28, מאת Eugene <prince...@gmail.com>:

ג'קי צ'אני‎

unread,
Jun 23, 2010, 10:59:53 AM6/23/10
to Computational Complexity, Spring 2010
עינת, למה סעיף ג זה לא נכון?
על כל פעולה מותר לנו להריץ מכונה שפותרת ב-
NP
אם מתרגמים אותה לזמן ריצה במכונה רגילה מקבלים מכונה דטרמיניסטית רגילה
שרצה בזמן 2 בחזקת או של אן בחזקת קיי כלשהו.
ואז בסה"כ זה אומר שלכל פעולה של האקספ מותר גם לבצע עוד מספר
אקספוננציאלי של פעולות.
ואז בסה"כ זה אקספוננציאלי, לא?

לא הבנתי את זה...


On Jun 23, 5:41 pm, Einat Kreiczer <einat...@gmail.com> wrote:
> הוא ענה על זה אתמול בתרגול חזרה, התשובה הנכונה היא ב'.
> השיטה שאיתה פסלו את תשובה ד' היא בעזרת בעיה שלא למדנו בסמסטר הנוכחי ולכן לא
> צריכים לדעת.
>

> בתאריך 23 ביוני 2010 17:28, מאת Eugene <princeeug...@gmail.com>:

Einat Kreiczer

unread,
Jun 23, 2010, 11:02:40 AM6/23/10
to computational-comp...@googlegroups.com
סעיף ג' שקול ל NEXP האוראקל NP נותן כוח אי דטרמינסטי.


בתאריך 23 ביוני 2010 17:59, מאת ג'קי צ'אני <mora...@gmail.com>:
Reply all
Reply to author
Forward
0 new messages