בתשובה לענק עדין, 05/02/08 0:16
 |
|
 |
||
|
||||
 |
אני לא מכיר דוגמא "מעניינת" (אולי כי בעיה כזו הייתה כבר נזנחת מזמן). מה כן? בעיית מגדלי האנוי מובאת תמיד בתור דוגמה לבעיה שהפתרון שלה (רשימת הצעדים שצריך לבצע כדי לפתור את המגדל) יהיה אקספוננציאלי בהכרח. כמובן שזה "לא מעניין" כי כאן ידוע בדיוק איך לפתור ורק ביצוע הפתרון עצמו הוא אקספוננציאלי. יש מה שנקרא "משפטי היררכייה" לסיבוכיות שמבטיחים קיום בעיה שאפשר לפתור רק בסיבוכיות (זמן/זכרון) גדולה כרצוננו, כל עוד הפונקציה היא "נורמלית" (2 בחזקת n זו פונקציה נורמלית, לצרכנו). ההוכחה היא בשיטת לכסון ובאופן כללי לא נותנת ביד שום בעיה ידועה ומעניינת. TQBF [Wikipedia] היא בעיה חביבה למדי שמאוד לא סביר שתהיה ב-NP, אבל לא באמת ידוע; היא מה שנקרא PSPACE-שלמה, שזה כמו NP-שלמה רק עבור מחלקה (כנראה) גדולה יותר, של כל הבעיות שאפשר לפתור בסיבוכיות *זכרון* פולינומית. היא די דומה באופיה ל-SAT, למי שמכיר, רק שכאן יש לנו נוסחה בתחשיב *הכמתים*. כאמור, ייתכן ש-P=PSPACE ואז בפרט זו בעיית NP; אבל זה מאוד מאוד לא סביר. מקום טוב אחד להתחיל לחפש בו דוגמאות לבעיות קשות "ממש" הוא "אלגוריתמיקה" של דוד הראל, שלצערי לא לידי כרגע. |
 |
 |
 |
|
|
|
||
|
||||
|
אהבתי במאמר שלך את תמונת החרוזים |
|
|
|
|
|
|
||
|
||||
|
חשבונייה, קראו לזה פעם. | |
|
|
|
|
|
||
|
||||
|
והנה אתר שמוקדש לו: http://www.ee.ryerson.ca/~elf/abacus/ | |
|
|
|
|
|
||
|
||||
|
בהמשך לדיון על אאופמיזם: זו לא מילה אנגלית! זו מילה לטינית, ממקור יווני עם ניחוח שמי, והיא משותפת לכל שפות אירופה. די לאנגלוצנטריות! | |
|
|
|
|
|
||
|
||||
|
פשוט מקורה בלטינית (לא כתבתי בשום מקום שזו מילה *רק* באנגלית). | |
|
|
|
|
|
||
|
||||
|
קראתי פעם שמקורה במלה ''אבק''. | |
|
|
|
|
|
||
|
||||
|
זאת אומרת, אם מאמינים לזה: או שמא בפיניקית: |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |