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