בתשובה לגדי אלכסנדרוביץ', 19/01/08 8:19
 |
|
 |
||
|
||||
 |
כמובן. הבעיה היא לא בP כי אין לאלגוריתם דטרמיניסטי דרך לפתור אותה בזמן פולינומי (נובע מההוכחה על האנוי), אבל בהינתן הפתרון, וידוא שלו (רק במהלך הראשון) כן נעשה בזמן פולינומי, לכן היא בNP, מה שהיה מפריך את P=NP אם הבעיה היתה תקפה. השאלה שלי היא למה בדיוק הבעיה לא תקפה ? |
 |
 |
 |
|
|
|
||
|
||||
|
אני לא בטוח מה הכוונה ב"לא תקפה". על כל פנים, שים לב שיש כמה הבדלים מהותיים בינה לבין בעיות חישוביות "רגילות" - בפרט, זו בעיה של חיפוש, לא של תשובת "כן/לא", אבל בעיקר (וזה ההבדל המהותי) - היא מבוססת על קלט *חלקי*, שיש בו מידע מוסתר - בעצם, מעין "קופסה שחורה" שצריך להתמודד איתו. הכוונה היא שיכולים להיות שני קלטים שנראים זהה למכונה, ובכל זאת "מתנהגים" שונה (על סמך מהי הדיסקית המסומנת). נראה לי שכאן נמצא ההבדל המרכזי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |