שאלות 3,4 גירסה 1
9 views
Skip to first unread message
kiri...@gmail.com
Aug 9, 2009, 4:57:05 AM8/9/09
to Complexity Course, Spring 2009, Tel Aviv University
(3) התשובה הנכונה היא PSPACE.
אך אם ידוע כי סרט הקריאה הוא גם סרט הכתיבה, כלומר סרט העבודה נמצא
באותו מקום ולא נוצר סרט קריאה חדש, מדוע מתייחסים למקום הנדרש למכונה
בתור "מקום חדש שהמכונה מנצלת"?
אך אם ידוע כי סרט הקריאה הוא גם סרט הכתיבה, כלומר סרט העבודה נמצא
באותו מקום ולא נוצר סרט קריאה חדש, מדוע מתייחסים למקום הנדרש למכונה
בתור "מקום חדש שהמכונה מנצלת"?
(4)התשובה הנכונה היא coNP, אך אם המכונה היא הסתברותית ויכולה להיות
מוכלת ב-PH, מדוע מובטח כי היא תרוץ בזמן פול' על ביטים רנדומיים?
Oren Z
Aug 9, 2009, 5:17:16 AM8/9/09
to Complexity Course, Spring 2009, Tel Aviv University
לגבי 4, נדמה לי שזה בזכות החלק של "תוך t צעדים" - אתה מגביל את זמן
הריצה של המכונה ל t צעדים וזה פול' באורך הקלט שלך.
הריצה של המכונה ל t צעדים וזה פול' באורך הקלט שלך.
Reply all
Reply to author
Forward
0 new messages