cc08b-quiz_Tue_v1 question 5

[אלכס‎]

Can somebody explain why the answer is is b?
Isn't TQBF ESPECIALLY-PSPACE-COMPLETE?

[Tal]

כשהוכחנו שהיא פיספייס-שלמה השתמשנו ברדוקציה בזיכרון לוגריתמי, וראיתי
איפשהו שפיספייס סגורה לרדוקציה במקום לוגריתמי, ושרדוקציה במקום
פולינומי חזקה מדי (אבל לא ראיתי הסבר ולא נראה לי שזה היה בשיעור).
בהנחה שזה נכון, לא מספיק שהרדוקציה בזמן פולינומי כפי שהוגדר בשלמות
במיוחד.

[Adi Glucksam]

זה לש משנה בכלל. הבעיה היא שהטענה בשאלה היא שקיים c קבוע כך שכל הרדוקציות אליה רצות בזמן O(n^c) זה נכון שהרדוקציה לוגריתמית, אבל logspace מוכלת בP, ולא בTime עם n^k עבור k כלשהו.

2010/7/24 Tal <talo...@hotmail.com>

[Tom]

כלומר, הבעיה היא שדורשים "לקבוע" את
c
?

או בצורה אחרת - אם היו דורשים רדוקציה ב
O(poly(n))

אז
TQBF
כן הייתה
PSPACE-COMPLETE

?

On Jul 24, 9:54 am, Adi Glucksam <adigluck...@gmail.com> wrote:
> זה לש משנה בכלל. הבעיה היא שהטענה בשאלה היא שקיים c קבוע כך שכל הרדוקציות
> אליה רצות בזמן O(n^c) זה נכון שהרדוקציה לוגריתמית, אבל logspace מוכלת בP,
> ולא בTime עם n^k עבור k כלשהו.
>

> 2010/7/24 Tal <taloo...@hotmail.com>

[Adi Glucksam]

בדיוק, זו ההגדרה של רדוקציה פולינומיאלית :)

Adi Glucksam
Nobody expects the Spanish inquisition
(not even me...)

2010/7/24 Tom <tomte...@gmail.com>

[Tom]

באותו בוחן, מישהו יכול להסביר את שאלה 6 בבקשה (מבחינת הפיתרון...)?

תודה

On Jul 24, 11:15 am, Adi Glucksam <adigluck...@gmail.com> wrote:
> בדיוק, זו ההגדרה של רדוקציה פולינומיאלית :)
>
> Adi Glucksam
> Nobody expects the Spanish inquisition
> (not even me...)
>

> 2010/7/24 Tom <tomtema...@gmail.com>

[Adi Glucksam]

אנחנו יודעים שגם NP וגם P סגורות לכוכב אז מה שמעניין פה זה למעשה משלים.

כל אורקל מחזיר אם הקלט שהוא קיבל הוא בשפה או לא, לכן אורקל לא משנה את הסגירות למשלים. מה שנשאר לעשות הוא להבין אילו מהמחלקות אנחנו יודעים שסגורות למשלים וזה המחלקות הדטרמיניסטיות משום שNPSPACE=PSPACE הרי שהתשובה היא ב+ג (שזה ה אם אני לא טועה).

Adi Glucksam

2010/7/24 Tom <tomte...@gmail.com>

[Ofir]

ומאיפה אנחנו יודעים שPSPACE סגור לכוכב?

On 24 יולי, 12:17, Adi Glucksam <adigluck...@gmail.com> wrote:
> אנחנו יודעים שגם NP וגם P סגורות לכוכב אז מה שמעניין פה זה למעשה משלים.
>
> כל אורקל מחזיר אם הקלט שהוא קיבל הוא בשפה או לא, לכן אורקל לא משנה את
> הסגירות למשלים. מה שנשאר לעשות הוא להבין אילו מהמחלקות אנחנו יודעים שסגורות
> למשלים וזה המחלקות הדטרמיניסטיות משום שNPSPACE=PSPACE הרי שהתשובה היא ב+ג
> (שזה ה אם אני לא טועה).
> Adi Glucksam
>

> 2010/7/24 Tom <tomtema...@gmail.com>

[Adi Glucksam]

עושים את ההוכחה בNPSPACE

מוסיפים מעבר אפסילון, אבל בגלל שNPSPACE=PSPACE

אז הוא סגור לשרשור גם כן.

Adi Glucksam
Nobody expects the Spanish inquisition
(not even me...)

2010/7/24 Ofir <ofir....@gmail.com>

[Ofir]

"מעבר אפסילון" D-:
זה כ"כ מודלים

On 24 יולי, 13:10, Adi Glucksam <adigluck...@gmail.com> wrote:
> עושים את ההוכחה בNPSPACE
> מוסיפים מעבר אפסילון, אבל בגלל שNPSPACE=PSPACE
> אז הוא סגור לשרשור גם כן.
> Adi Glucksam
> Nobody expects the Spanish inquisition
> (not even me...)
>

> 2010/7/24 Ofir <ofir.isr...@gmail.com>