 |
P מלשון "פולינום". הרעיון הוא שפולינום הוא פונקציה שגדלה בקצב סביר (יחסית למפלצת שנקראת "פונקציה אקספוננציאלית"). עוד כמה תכונות נחמדות של פולינומים גרמו לכך שנבחר את כל הבעיות שאפשר לפתור בזמן פולינומי בתור המחלקה שלנו שאמורה לייצג את הבעיות שניתנות לפתרון בצורה יעילה.
NP זה מה שמקבלים כשמרשים חישוב לא דטרמיניסטי (N מלשון Nondeterminism). פירוש החישוב הלא דטרמיניסטי הוא שבמהלך הנסיון להכריע את הבעיה מותר להשתמש ב"הטלת מטבע" קסומה. ה"קסם" מתבטא בכך שהטלת המטבע תמיד תעזור לנו.
דוגמה: אני רוצה לפרק מספר למחלקים הראשוניים שלו. נניח, את 143 ל-11 כפול 13. דרך אחת היא פשוט להתחיל לעבור על מספרים ולבדוק עבור כל אחד מהם אם הוא מחלק אותו. זה ייקח המון זמן כי יש המון מספרים (גם אם מצליחים לצמצם את הטווח על ידי בדיקה רק של המספרים עד השורש וכל מני טריקים דומים). הדרך ה"אי דטרמיניסטית" היא "להטיל מטבע" - לבחור באקראי מספר ולבדוק אם הוא מחלק. מכיוון שהטלת המטבע היא קסומה, מובטח לנו שאם קיים מספר שמחלק את 143, נצליח לנחש אותו בהטלת המטבע הזו.
נשמע מופרך? כן, נו, זה למה NP מכיל בעיות שלא יודעים כרגע איך לפתור בצורה יעילה.
דרך אחרת לגמרי לחשוב על זה, בלי אי דטרמיניזם וגועל נפש דומה: P אלו כל הבעיות שאנחנו יודעים לפתור בצורה יעילה. NP אלו כל הבעיות שאם כבר מישהו בא והציע פתרון אליהן, אפשר לבדוק בצורה יעילה אם הפתרון נכון או לא (למשל, אם מישהו בא ואומר "פירקתי את 143! המחלקים שלו הם 11 ו-13!" פשוט אפשר לכפול ולראות מה קיבלנו).
אולי באמת הגיע הזמן למאמר.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש