בתשובה לגדי אלכסנדרוביץ', 14/05/06 14:11
מה שירדן אמר, בערך. 385239
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 18:24
אולי אני מפספס משהו ממש בסיסי אבל אני לא משוכנע שזה נכון. אתה יכול לחשוב על הוכחה? נניח שהמודל שלנו הוא מכונת טיורינג (או כל מודל אחר שאתה מעדיף).
מה שירדן אמר, בערך. 385242
גדי אלכסנדרוביץ' • בתשובה למ. השור יום א', 14/5/2006, 18:44
אתה לא משוכנע שמה נכון? שקיימות בעיות שהפתרון שלהם הוא חזקה בגודל הזה? זו תוצאה של מה שמכונה Time hierarchy theorem.

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

אולי ההוכחה שיש בויקיפדיה האנגלית כן קונסטרקטיבית:
מה שירדן אמר, בערך. 385250
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 19:12
אתה צודק. זכרתי שיש משפט היררכיה של המקום אבל לא משפט היררכיה (פולינומי) של הזמן. טעות שלי.
מה שירדן אמר, בערך. 385253
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 19:26
עד כמה שאני מבין (למרות שאני קצת פחות סומך על עצמי כרגע) ההוכחה (שאני מכיר) היא כן קונסטרוקטיבית. מוכיחים ששפת כל המכונות M והקלטים x כך ש- M מקבלת את x בפחות מ- f(|x|) צעדים היא כריעה בזמן f^3 (נגיד) ולא כריעה בזמן f(n/2).

לכן לכל n^k קל להראות שפה פולינומית שלא חשיבה ב- n^k.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות