PH ו- PSPACE

31 views
Skip to first unread message

Erez

unread,
Jun 24, 2010, 3:56:12 PM6/24/10
to Computational Complexity, Spring 2010
כשאני חושב על זה אני לא ממש מבין מה ההבדל ביניהן..
הרי ט.ק.ב.ף. היא פיספייס-שלמה ואפשר לכתוב אותה כביטוי מהצורה של פי-
הייץ'.
אולי בגלל שצריך לקבוע קבוע מסויים וט.ק.ב.ף זה לכל מספר של כמתים ?

אבל לא ידוע האם פי-הייץ' מוכלת ממש בפיספייס, ככה שזה לא זה.

Eyal Dushkin

unread,
Jun 24, 2010, 4:25:21 PM6/24/10
to Computational Complexity, Spring 2010
בגדול האינטואיציה שלך נכונה.
המחלקה PH מאד קרובה ל-PSPACE, למעשה היא ו-PSPACE מכילות אולי את כל
השפות שלמדנו במסגרת הקורס.
אבל (!) זה לא נכון ש-TQBF שייכת למחלקה PH.

TQBF מקבלת כקלט n משתנים עם n כמתים ואיזשהי נוסחא פי.
שים לב לעניין העדין של הכימות - נניח ש-TQBF שייכת ל-PH, אז לפי הגדרה
קיים איזשהו K כך ש-TQBF שייך לסיגמאK. עתה קח פשוט את TQBF עם K+1
משתנים, ואז זאת בעייה קשה להכריע את TQBF בסיגמאK.

יחד עם זאת בהחלט קיים דמיון ובאחד המבחנים אפילו הגדירו שפה TQBF-C
שהייתה באמת בסיגמאC.

Erez

unread,
Jun 24, 2010, 4:57:31 PM6/24/10
to Computational Complexity, Spring 2010
זה גם מה שאני חשבתי.
אבל אם זה ככה למה זה לא מוכיח שהמחלקות שונות ?
ואם אני לא טועה, לא ידוע אם הן שוות..

Eyal Dushkin

unread,
Jun 24, 2010, 5:05:58 PM6/24/10
to Computational Complexity, Spring 2010
ממש לא.
תראה - זה שאנחנו לא הצלחנו לפתור את זה ב-PH לא אומר שאי אפשר :-) זה
פשוט קצת קשה.
מאד קל לפתור את TQBF עם C כמתים בסיגמאC או אם להיות יותר מדוייקים,
עדיף לעבוד בסיגמאC+1 כדי לתת עוד השמות למשתנים החופשיים (אעפ"י שנראה
שאפשר לדחוף אותן בין הקיימים).
זה שעבור TQBF הרגיל זה לא עובד, לא אומר כמובן שהמחלקות שונות, זאת פשוט
שאלה פתוחה - אם תצליח להוכיח הכלה ממש או להקריס את ההיררכיה מה טוב.
Reply all
Reply to author
Forward
0 new messages