בתשובה לקהלת, 12/05/06 19:00
 |
|
 |
||
|
||||
 |
SAT זו בעיה ששייכת ל-NP. כלומר, כרגע אנחנו לא יודעים לפתור אותה בצורה יעילה אבל אם נוכיח ש-P=NP כן נדע. החוכמה בה היא שגם ההפך נכון - אם נדע לפתור אותה בצורה יעילה נוכל לפתור כל בעיה אחרת ב-NP בצורה יעילה. TQBF זה אותו הדבר, רק עבור הגדרה אחרת של "יעילה" - במקום שנמדוד את הזמן, מודדים את הזכרון. האוסף של כל הבעיות שאפשר לפתור בזכרון יעיל נקרא PSPACE (ה-P בהתחלה זה כמו ה-P בP=NP, ה-SPACE אחר כך בא מ"זכרון", או "מקום"). יש כל מני בעיות שקיימות ב-PSPACE אבל לא ברור אם שייכות ל-NP. כלומר, גם אם נראה ש-P=NP זה עדיין לא אומר שאפשר לפתור אותן בזמן יעיל. בכל זאת, אלו בעיות שלא בלתי סביר שנרצה להיות מסוגלים לפתור גם אותן (TQBF היא הבעיה של לקבל נוסחה לוגית מכומתת בלי משתנים חופשיים ולהחליט אם היא בעלת ערך אמת או שקר). אולי הגיע הזמן למאמר בנושאים הללו באייל? |
 |
 |
 |
|
|
|
||
|
||||
|
ומהו ה-P ב-NP? מה פתאום הרעיון של P=NP? | |
|
|
|
|
|
||
|
||||
|
P מלשון "פולינום". הרעיון הוא שפולינום הוא פונקציה שגדלה בקצב סביר (יחסית למפלצת שנקראת "פונקציה אקספוננציאלית"). עוד כמה תכונות נחמדות של פולינומים גרמו לכך שנבחר את כל הבעיות שאפשר לפתור בזמן פולינומי בתור המחלקה שלנו שאמורה לייצג את הבעיות שניתנות לפתרון בצורה יעילה. NP זה מה שמקבלים כשמרשים חישוב לא דטרמיניסטי (N מלשון Nondeterminism). פירוש החישוב הלא דטרמיניסטי הוא שבמהלך הנסיון להכריע את הבעיה מותר להשתמש ב"הטלת מטבע" קסומה. ה"קסם" מתבטא בכך שהטלת המטבע תמיד תעזור לנו. דוגמה: אני רוצה לפרק מספר למחלקים הראשוניים שלו. נניח, את 143 ל-11 כפול 13. דרך אחת היא פשוט להתחיל לעבור על מספרים ולבדוק עבור כל אחד מהם אם הוא מחלק אותו. זה ייקח המון זמן כי יש המון מספרים (גם אם מצליחים לצמצם את הטווח על ידי בדיקה רק של המספרים עד השורש וכל מני טריקים דומים). הדרך ה"אי דטרמיניסטית" היא "להטיל מטבע" - לבחור באקראי מספר ולבדוק אם הוא מחלק. מכיוון שהטלת המטבע היא קסומה, מובטח לנו שאם קיים מספר שמחלק את 143, נצליח לנחש אותו בהטלת המטבע הזו. נשמע מופרך? כן, נו, זה למה NP מכיל בעיות שלא יודעים כרגע איך לפתור בצורה יעילה. דרך אחרת לגמרי לחשוב על זה, בלי אי דטרמיניזם וגועל נפש דומה: P אלו כל הבעיות שאנחנו יודעים לפתור בצורה יעילה. NP אלו כל הבעיות שאם כבר מישהו בא והציע פתרון אליהן, אפשר לבדוק בצורה יעילה אם הפתרון נכון או לא (למשל, אם מישהו בא ואומר "פירקתי את 143! המחלקים שלו הם 11 ו-13!" פשוט אפשר לכפול ולראות מה קיבלנו). אולי באמת הגיע הזמן למאמר. |
|
|
|
|
|
|
||
|
||||
|
בחור מסוכן. אתה מתחיל להתחרות בעוזי בעניין ההוראה! | |
|
|
|
|
|
||
|
||||
|
קדימה. | |
|
|
|
|
|
||
|
||||
|
תודה | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |