סיבוכיות: זקוק נואשות לכיוון.

[shirbi]

סיבוכיות: זקוק נואשות לכיוון.

קיבלתי שאלה לשיעורי הבית שאין לי מושג איך לענות עליה (ולפי מה שהבנתי, אף אחד אחר בקורס לא הצליח עדין): צריך להוכיח ש PSPACE שונה מהשפה הבאה: איחוד DTIME של 2 בחזקת c*n, עבור c מ 1 ועד אינסוף. הכיוון הוא כנראה להראות ש PSPACE גדולה יותר (ולא להיפך): למה? לדוגמה, מ"ט הרצה בזיכרון O של n בריבוע - השפה שלה כמובן שייכת ל PSPACE, אולם מספר הקונפיגורציות שלה יכול להגיע גם לסדר גודל של 2 בחזקת (n בריבוע), כלומר היא לא מתאימה לאיחוד ה DTIME הנ"ל. זו כמובן לא הוכחה שאי אפשר לחשב את השפה של המכונה באמצעות מכונה אחרת, יותר יעילה מבחינת סיבוכיות זמן, אבל נראה לי שזה רומז על הכיוון. יש למישהו רעיון איך עושים זאת? אולי למשל להראות שהאיחוד הנ"ל מוכל בתוך אוסף השפות המתקבלות ע"י מ"ט הרצה בזיכרון O של n בחזקת k עבור k חסום כלשהו, ואז ע"פ משפט היררכיה, נקבל ש PSPACE גדולה יותר? או ליכסון כלשהו? או ניפוח? תודה מראש.

 

[johnny d]

אם זה הכיוון שלך אז תחשוב אולי

על מכונה דטרמינסטית שזמן הריצה שלה הוא n^n המחשבת משהו במקום פולינומיאלי. חשוב כמובן להבין כי המספר n^n יכול להיות מיוצג ע"י n*log n סיביות שזהו מקום פולינומיאלי. והמספר המיוצג אינו שייך ל EXP, שזו דרך אגב המחלקה שאתה מתאר.

 

[shirbi]

רגע, רגע!

המחלקה שאני מתאר יותר קטנה מ EXP EXP כוללת את האיחוד האינסופי של המחלקות DTIME של 2 בחזקת (n בחזקת c) עבור c מ 1 עד אינסוף. לעומת זאת המחלקה שאני מדבר עליה כוללת את האיחוד האינסופי של המחלקות DTIME של 2 בחזקת (c כפול n).

 

[ron369]

הנה

מה בעצם אנחנו צריכים? ומה אנחנו יודעים? צריכים: אנחנו צריכים, איכשהוא, למצוא מ"ט דט', כך שהזיכרון שלה הוא, איכשהוא, פולינומיאלי, אך, איכשהוא, היא רצה בזמן שהוא גדול מ-2 בחזקת cn. כלומר, למשל, נניח: 2 בחזקת n בריבוע. יודעים: אנחנו יודעים שהבעיה PSPACE=EXPTIME מאד קשה, ככל הנראה, אך שמתקיימת ההכלה: EXPTIME≥PSPACE. נזכר בסיבה להכלה זו. נניח שנתונה בעיה עם זיכרון פולינומיאלי, משמע: poli. עכשיו, מספר הקונפיגורציות האפשריות של מצבי המכונה, הוא בערך, מקומבינטוריקה פשוטה, ((k כפול p) בחזקת (poli). כאשר k הוא מספר מצבי המכונה, p הוא מספר התווים שיכולים להופיע בכל מיקום בסרט, וpoli הוא גודל הזיכרון שנשתמש בו. עכשיו, ברור שיכול להיות ש-poli אינו לינארי ב-n, ולכן שמספר מצבי המכונה הוא, בעצם, בערך, 2 בחזקת poli. כלומר, מה שאנחנו צריכים למצוא הוא אלגוריתם, שמכיל מעבר על, למשל, כל הקונפיגורציות על שטח זיכרון של n^2 (אן בחזקת 2, ולא 2 בחזקת n!!!). ועכשיו, התוצאה היא אלגוריתם שעובר בכל ריצה על 2 בחזקת (n בחזקת 2) קונפיגורציות, משמע, אינו במחלקה שבשאלה, אך בPSPACE. איך עושים את זה? מושאר כתרגיל לקורא הנאמן והמפחד מ-0 בקורס.

 

[shirbi]

זה נשמע רעיון טוב, אבל, איך מוצאים

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

 

[ron369]

מצטער, טעיתי. לא התייחסתי לשאלה

ברצינות, וחשבתי שאני יודע את הפתרון לפני שאני מסיים לקרוא אותה

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

 

[shirbi]

אז יש לך איזה רעיון לפתרון?

 

[ron369]

לא ממש ../images/Emo10.gif

 

[shirbi]

נקודה למחשבה:

האם באמת הכיוון שאני הולך בו הוא הכיוון הנכון ולא להפך? כלומר, אולי עלי להראות דווקא שהאיחוד הנ"ל (נקרא לו מעתה K) מכיל שפה שאיננה ב PSPACE? הסבר: ידוע ש P מוכל ב PSPACE אולם לא ידוע אם זו הכלה ממש או שוויון. בנוסף, באמצעות משפט היררכיה, ניתן להראות ש P מוכל ממש ב K. לכן, אם K מוכל ב PSPACE, אז בוודאי ש P מוכל ממש ב PSPACE. לכן סביר ש K לא מוכל ב PSPACE, כלומר ישנה שפה הנמצאת ב K ולא נמצאת ב PSPACE.

 

[ron369]

נכון, אבל אם קיימת שפה הנמצאת ב-K

ולא ב-PSPACE, אזי השפה הזו לא נמצטת ב-PSPACE גם כאשר השפה נמצאת ב-EXP. כלומר - אם נוכיח הכלה לגבי K בכל אחד משני התחומים, נגיע לפתרון של בעיה קשה. לסיכום: 1) אם K מוכל בPSPACE ממש (הרי בהכרח הן שונות לפי השאלה), אזי נוכל להסיק שK מוכל ב-P ממש. 2) אם PSPACE מוכל ב-K ממש, אזי נוכל להסיק שPSPACE מוכל ב EXP ממש. ולכן, סביר להניח שאנחנו לא צריכים להוכיח הכלה ממש.

 

[shirbi]

זה עוד יותר גרוע:

אם אני מוצא שפה שנמצאת ב PSPACE ולא נמצאת ב K, אז הוכחתי ש PSPACE שונה מ P. אם אני מוצא שפה שנמצאת ב K ולא נמצאת ב PSPACE, אז הוכחתי ש PSPACE שונה מEXPTIME. שתי הבעיות הללו, כפי שכבר הזכרת, הן מאוד קשות, ולא סביר שאקבל אותן כתרגיל בית ראשון בקורס (אלא אם וויני צודק לגבי הרצון של המרצים בטכניון להתעלל בסטודנטים). אז מה בעצם אפשר לעשות כאן? אולי איכשהו להשתמש בעקרון הניפוח כלפי מעלה? האם לא אגיע בצורה כזאת שוב לתוצאה ש P שונה מ PSPACE או ש PSPACE שונה מ EXPTIME? איך אפשר להראות שונות בין שתי קבוצות בלי להראות איבר שנמצא באחת מהקבוצות ולא נמצא בשניה? הרי אני לא יכול להשתמש בלכסון כמו שמראים שקבוצת הממשיים שונה מקבוצת הטבעיים בגודלה, שכן בכל מקרה, הגודל של כל הקבוצות שאני מדבר עליהם הוא בן מניה.

 

[shirbi]

ובכן, יש פתרון!

הרעיון הוא להראות תכונה שמתקיימת עבור PSPACE אבל לא מתקיימת עבור K. אם מישהו רוצה שארחיב, שיגיד.