בתשובה להאייל האלמוני, 12/06/08 16:09
 |
|
 |
||
|
||||
 |
אני אמנם לא מתמצא במיוחד במודלים לא יוניפורמיים, אבל אתה יכול לתת דוגמא לשימוש במודל כזה בהקשר של חישוביות ולא של סיבוכיות. כי נראה לי שכל המודלים הללו הם טריוויאליים מבחינת החישוביות (דהיינו, הכל חשיב בהם). |  |
 |
 |
|
|
|
||
|
||||
|
הכל? בהחלט לא, כי מגבילים את גודל ה"רמז" שהמכונה מקבלת להיות פולינומי. הדוגמה הקלאסית היא המחלקה P/poly (מכונה פולינומית/רמז פולינומי לכל גודל קלט) שמכריעה שפות לא כריעות ולכן מהווה מודל "דמיוני", אבל לא מסוגלת להכריע כל דבר, ולכן עדיין מעניינת (בתור "חסם עליון" על מה שכן אפשר להכריע, כי היא מכילה את BPP). |
|
|
|
|
|
|
||
|
||||
|
תודה, אבל זה עדיין רמאות: כמו לקרוא ל- P מודל חישובי. | |
|
|
|
|
|
||
|
||||
|
זה דומה, אבל אני לא מסכים שזה זהה (כאן זו שאלה של גודל התיאור, לא של כמה משאבים אנחנו מרשים למכונה לצרוך). מצד שני, מדובר כאן על הבדל שהוא פילוסופי בעיקרו ואנחנו ממילא באותו צד אז לא נריב. | |
|
|
|
|
|
||
|
||||
|
זה נכון. צריך להגדיר טיפה יותר טוב מה זה ''המודלים האלו'' ומה זה אומר ''הכל חשיב בהם''. אם אתה מרשה מעגלים בגודל אקספוננציאלי מספיק גדול או לחילופין קלט בייצוג אונארי, אכן הכל חשיב. הדוגמא שנתתי באמתת מסתמכת על מחלקת סיבוכיות המוגדרת באמצעות המודל הזה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |