בתשובה להפונז, 23/06/15 14:46
 |
|
 |
||
|
||||
 |
א. אם בהנתן סידור אתה יכול לדעת אם הוא טוב או לא אז הבעיה היא ב- NP. ב. יש בעולם הרבה בעיות יותר קשות מ- NP. |
 |
 |
 |
|
|
|
||
|
||||
|
א. ברור שלא (אתה לא יכול). וודאי לא א-פריורי. ב. כן, ידעתי שאני מתרשל כאן. לא הייתי לוקח את האמירה ההיא באופן מתימטי. |
|
|
|
|
|
|
||
|
||||
|
א. אתה טוען שהבעיה בכלל לא פתירה? בעיות לא פתירות הן לא ב- NP, אבל זו לא חוכמה. נגיד שנתנו לך כמות משאבים בלתי מוגבלת, האם היית יכול למצוא סידור טוב? ב. לקיחת אמירות באופן מתמטי זה התפקיד שלי. אין צורך להודות לי, אני כאן למענכם. |
|
|
|
|
|
|
||
|
||||
|
א. תלוי מהי הגדרת הבעיה. האם מדובר על סידור (מספיק) טוב או סידור אופטימלי. בהנתן סידור אתה יכול לבדוק שהוא מספיק טוב, אבל לא יכול לוודא שהוא אופטימלי. ב. אנחנו תמיד שמחים לארח כאן את ראש ממשלת יוון. |
|
|
|
|
|
|
||
|
||||
|
א. האם אפשר לתת מספר בתחום סופי שמתאר את "איכות הסידור"? כלומר בהנתן סידור, אני יכול למצוא באופן יעיל את איכותו? אם כן אז בעיית הסידור האופטימלי היא ב- NP. גם אם לא, כל עוד יש יחס סדר בין הסידורים (כלומר אפשר להגיד האם א' עדיף על ב'), הבעיה תהיה לכל היותר במחלקה סיגמא-2 שהיא קצת מעל NP 1. אבל עדיין הרבה יותר קלה מבעיות כמו דמקה או אפילו איקס-עיגול אסימפטוטיים 2. ב. העונג כולו שלי, או כמו שאומרים אצלנו ביוון: "פיראוס פטה אנטיגונה סופוקלס שחוציאניטיס". ________ 1 או הרבה מעל, או בכלל לא מעל, תלוי את מי אתה שואל. 2 או קצת יותר קלה, או בכלל לא יותר קלה, תלוי את מי אתה שואל. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |