בתשובה לאביב י., 25/09/05 3:47
 |
|
 |
||
|
||||
 |
לדעתי, בקצרקורס-מזורז-רצחים עדיף להשתמש בהגדרה אחרת ל־P ו¯NP (שקולה): P היא קבוצת הבעיות שניתן למצוא להן פתרון ביעילות (בזמן פולינומי). NP היא קבוצת הבעיות שניתן לוודא ביעילות האם משהו הוא פתרון שלהן או סתם קשקוש. בהצגה הזאת, כל בר דעת מבין ש־NP הרבה יותר גדולה מ־P, וקולט את התסכול של מדעני המחשב שכבר 40 שנה לא מצליחים להוכיח כזה דבר ברור. |
 |
 |
 |
|
|
|
||
|
||||
|
אכן, גם אני אוהב יותר את הפשטות שבההגדרה הזאת של NP, אם כי אני לא שותף להרגשה שנביעת גודלה של NP מכך זה "כזה דבר ברור" (אם כי אני לא בטוח שבר דעת אנוכי). אבל אולי כדאי לחזור לנושא הדיון המעניין, לפני ששדמי יצוץ פה ויוכיח ש-NP מוכלת *ממש* ב-P, באמצעות מ"ט בעלת קבוצת מצבים מלאה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |