בתשובה לעדי סתיו, 12/05/06 11:25
 |
|
 |
||
|
||||
 |
מה ישמח אותך יותר - P=NP או P≠NP? |  |
 |
 |
|
|
|
||
|
||||
|
זה אומר שניתן לחשב כמעט כל דבר מעניין. | |
|
|
|
|
|
||
|
||||
|
זה לא אומר בהכרח שזה משמח. פירוש הדבר, למשל, הוא שחלק משיטות ההצפנה שאנחנו משתמשים בהן כיום הופכות ללא רלוונטיות. (אילו שיטות הצפנה מבוססות על בעיות שלא יושפעו מהגילוי הזה?) אגב, אני לא כל כך בטוח בקשר ל"כמעט כל דבר מעניין". אולי SAT זה מעניין, אבל TQBF מעניין עוד יותר. ממש לשמוח אפשר אם מגלים ש-P=PSPACE. |
|
|
|
|
|
|
||
|
||||
|
אפשר בעברית ? | |
|
|
|
|
|
||
|
||||
|
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!" פשוט אפשר לכפול ולראות מה קיבלנו). אולי באמת הגיע הזמן למאמר. |
|
|
|
|
|
|
||
|
||||
|
בחור מסוכן. אתה מתחיל להתחרות בעוזי בעניין ההוראה! | |
|
|
|
|
|
||
|
||||
|
קדימה. | |
|
|
|
|
|
||
|
||||
|
תודה | |
|
|
|
|
|
||
|
||||
|
כפי שאתה בודאי יודע, גם אם P=NP יתכן שחלק משיטות ההצפנה שאנחנו משתמשים בהן כיום יהפכו ללא רלוונטיות. בכל מקרה, עד כמה שאני זוכר משהו מהקורס בשיטות הצפנה, יש שיטות הצפנה שבטיחותן מוכחת (שלא כמו RSA) ומכאן שגם אם P=NP הן ישארו בטוחות. | |
|
|
|
|
|
||
|
||||
|
מה עם הצפנה קוונטית (מבוססת על אי-שוויון בל)? | |
|
|
|
|
|
||
|
||||
|
זה זן אחר לגמרי של הצפנה, שאין לו כל קשר לשאלה P=NP. נדמה לי שאיזי כיוון לשיטות אלגוריתמיות. | |
|
|
|
|
|
||
|
||||
|
(לא ברור לי למה לא עניתי לזה קודם) נראה לי ש-easy כיוון כאן לשיטת הפנקס החד פעמי (שהיא *ה*שיטה שבטיחותה מוכחת, ועד כמה שהבנתי כל שיטה אחרת בעלת בטיחות מוכחת היא פשוט וריאציה עליה). פנקס חד פעמי [ויקיפדיה] |
|
|
|
|
|
|
||
|
||||
|
התכוונת בהתחלה ל-P≠NP, נכון? בכל מקרה, זו הזדמנות לתת דוגמאות. הן לשיטות שיהפכו ללא רלוונטיות גם אם P≠NP, והן לשיטות שלא יהפכו ללא רלוונטיות גם אם P=NP. |
|
|
|
|
|
|
||
|
||||
|
כמובן. כפי שאתה ודאי יודע, פירוק לגורמים הוא לא בעיה שלמה בNP, כלומר יתכן שיש לבעיה פתרון פולינומיאלי גם אם P≠NP. אני כבר לא זוכר מה למדתי בשיטות הצפנה, אבל היה משהו על היכולת לבנות פולינום מהפתרונות שלו לעומת חוסר היכולת לפתור פולינום (מדרגה מספיק גבוהה). |
|
|
|
|
|
|
||
|
||||
|
על פניו, מה שאתה אומר על פולינום נשמע כמו NP: אם קל לבנות פולינום מהפתרונות שלו, הרי שקל גם לוודא שהצלחנו לנחש את הפתרונות שלו (פשוט נבנה את הפולינום על פי הפתרונות ונשווה לפולינום שאנחנו מנסים לפתור). אולי הבעיה נובעת מזה שעלולים להיות המון פתרונות ביחס למשאבים שנדרשים לייצג את הפולינום, אבל אני לא בטוח אם לזה התכוונת. | |
|
|
|
|
|
||
|
||||
|
אני כבר באמת לא זוכר, אבל אם מציאת פתרונות של פולינומים היתה בעיה ב-NP, אז גלואה כבר הוכיח ש P≠NP. | |
|
|
|
|
|
||
|
||||
|
האם משנה דרך מציאת הפתרונות (אם לשים את הקלפים על השולחן - האם פתרון נומרי מספיק "טוב" להגדרה זו)? ובכל מקרה - מהי היעילות של שיטת ניוטון-רפסון (משולבת עם "ציד אריות", במידת הצורך)? | |
|
|
|
|
|
||
|
||||
|
אני לא יודע. (בכל מקרה יש לך את מגבלת הדיוק של המודל החישובי שלך, כך שכל ערך מספיק קרוב לפתרון הוא פתרון נומרי.) | |
|
|
|
|
|
||
|
||||
|
כדאי להיזהר עם מה שמייחסים לגלואה. גלואה הוכיח שלא ניתן לפתור *באמצעות רדיקלים* את *המשוואה הכללית* ממעלה חמישית ומעלה (וגם הצביע על דרך יפהפיה לדעת עבור כל משוואה האם היא פתירה באמצעות רדיקלים או לא). זה לא אומר שלא ניתן לפתור את המשוואה - זה תלוי בצורה שבה אתה מגדיר "פתרון". לעצם העניין, אם אתה מסוגל לייצג את השורשים בדרך כלשהי, אז גם אפשר לפתור את המשוואה ולקבל את השורשים באותה דרך ייצוג (עוברים על כל מרחב הפתרונות האפשריים בצורה סדרתית ועבור כל אוסף פתרונות בודקים אם הפולינום שנגזר ממנו הוא הפולינום שאת הפתרונות שלו מחפשים). כדאי גם לזכור שכשאנחנו חושבים על פולינומים אנחנו חושבים על פונקציות במספרים ממשיים, אבל אין ייצוג דיגיטלי למספרים ממשיים אלא רק לקירובים (רציונליים) שלהם. |
|
|
|
|
|
|
||
|
||||
|
פתרונות של פולינומים במקדמים שלמים הם לא כל הממשיים אלא רק המספרים האלגברים, שהם קבוצה בת מניה וניתנת ליצוג מדוייק במחשב (אבל בד''כ מעדיפים להשתמש בקרוב רציונלי). | |
|
|
|
|
|
||
|
||||
|
צודק, אבל זה רק משחק לטובתי: זו קבוצה בת מנייה ולכן אפשר לסרוק אותה באופן סדרתי (לפחות בתיאוריה). | |
|
|
|
|
|
||
|
||||
|
ברור, אבל אתה יכול להראות איך אתה מבצע סריקה כזאת במסגרת NP? | |
|
|
|
|
|
||
|
||||
|
אם הפולינום מדרגה n, אני מנחש n מספרים אלגבריים ובודק אם הם יוצרים את הפולינום. אם אתה רוצה משהו דטרמיניסטי, זה הופך לשאלה המעניינת של איך סורקים את הכל בצורה סדרתית, וזו שאלה טכנית שבשביל לענות עליה צריך לדעת מה הייצוג שלך למספרים אלגבריים. בצורה הכי פשוטה אפשר לעבור על כל הרצפים האפשריים של 0 ו-1, ועבור כל רצף ראשית לבדוק האם הוא מייצג מספר אלגברי חוקי, ואם כן אז אפשר לקחת אותו. |
|
|
|
|
|
|
||
|
||||
|
"בצורה הכי פשוטה אפשר לעבור על כל הרצפים האפשריים של 0 ו-1" - אתה בוודאי מתלוצץ. | |
|
|
|
|
|
||
|
||||
|
אה... לא. | |
|
|
|
|
|
||
|
||||
|
אני כנראה לא מבין אותך. רצפים סופיים? אינסופיים? | |
|
|
|
|
|
||
|
||||
|
סופיים. אני מניח (מן הסתם) שייצוג במחשב של מספר אלגברי הוא סופי. | |
|
|
|
|
|
||
|
||||
|
עכשיו אני מבין למה התכוונת. אתה צודק בעניין המנייה, אבל נדמה לי שאתה מפספס את העיקר. אתה מטאטא הצידה את שאלת הייצוג, אבל היא לב העניין: איך אתה מייצג מספרים אלגבריים ע"י מחרוזת של ביטים, והאם הייצוג מספיק יעיל כדי לבדוק שמחרוזת כזו מייצגת שורש של פולינום נתון בזמן פולינומיאלי באורך הקלט? ("אורך הקלט" הוא גודל הייצוג הבינארי, נניח, של מקדמי הפולינום). כל עוד לא הסברת את הפרטים הללו, לא ממש התקדמת בשאלה האם הבעייה היא ב-NP או לא. אפשר לחשוב על כמה ייצוגים אפשריים; אחד מהם הוא, פשוט, לייצג מספר אלגברי ע"י המקדמים של הפולינום המינימלי שלו מעל הרציונליים. מעבר לבעייה של האבחנה בין השורשים השונים של אותו פולינום אי-פריק, שאל את עצמך אם זו בכלל הבעייה אליה התכוונת - בשיטה הזו אנו "פותרים" את המשוואה p=0 (אם היא במקרה אי-פריקה) ע"י ציון העובדה הלא-מפתיעה ששורשיה הם אותם מספרים אלגבריים שהם שורשים של p. ייצוג אחר יכול, למשל, לבנות כל מספר אלגברי ממספרים רציונליים תוך שימוש בארסנל מצומצם ככל האפשר של פעולות. זה כבר יותר דומה למובן הקלאסי של "פתרון", ואם נשים בארסנל את ארבע פעולות החשבון, שורשים ו"אולטרא-שורשים" אכן נוכל לייצג כל מספר אלגברי. האם בייצוג הזה יש בכלל חסם פולינומי על אורך הפתרון כפונקציה של המקדמים? זה כלל לא ברור. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק, אבל שים לב שאני ו-easy גלשנו מתחומי הסיבוכיות לחישוביות כשהוא עירב את גלואה, ועל זה דיברתי. אם חוזרים לסיבוכיות, השאלה המשמעותית כאן לדעתי היא לא מה הייצוג שבא לנו לבחור, אלא מה הייצוג שדרוש עבור הצפנה. אם בשביל *לפענח* הודעה מוצפנת די לדעת את הייצוג על ידי מקדמי הפולינום, כמובן שההצפנה לא שווה כלום. לכן אמרתי קודם ש"אולי הבעיה נובעת מזה שעלולים להיות המון פתרונות ביחס למשאבים שנדרשים לייצג את הפולינום". אבל באמת, בשביל להגיד עוד על העניין הזה אני צריך לשמוע תיאור מפורט של השיטה. בינתיים אני מסתפק במה שאמרו גדולים ממני. |
|
|
|
|
|
|
||
|
||||
|
מהניסוח שלך משתמע שעצם מציאת הוכחה לכך ש-P=NP, די בה כדי להפוך שיטות הצפנה אופרטיביות ללא רלבנטיות. הטענה הזאת נראית לי לא טריוויאלית 1. התואיל להסביר מדוע זה כך? 1 הוכחות מתמטיות שעוסקות במקרים כלליים, אינן מציעות בהכרח שיטות סדורות למציאת פתרונות עבור מקרים פרטיים. |
|
|
|
|
|
|
||
|
||||
|
הבקיאות שלי בקריפטוגרפיה אפסית, אבל ככל הידוע לי, רוב שיטות ההצפנה שמשמשות אותנו כיום מתבססות על בעיות שהן ב-NP אבל לא ידוע אם הן ב-P. זה לא מקרי - אם משהו ב-NP זה אומר שהוא קל במובן אחד אבל לא בהכרח קל במובן שני - קל לבדוק לו פתרון, אבל לא בהכרח קל למצוא לו פתרון. באותו המובן אנחנו רוצים שמשהו יהיה קל לפענוח אם יודעים מה המפתח, אבל יהיה קשה למצוא את המפתח אם הוא לא ידוע. כמובן שאני מנפנף כאן ידיים. אני יכול גם לזמן תותח כבד בדמות "שאלתי מרצה לקריפטוגרפיה והוא אמר לי שזה ככה". עוד כמה סמסטרים, בתקווה, אני אוכל לענות יותר בפירוט. אגב, כדאי לזכור שטענה כמו P=NP תהיה מלווה *ככל הנראה* בהוכחה קונסרקטיבית - יודגם איך ניתן לפתור בעיה כלשהי שהיא NP שלמה בזמן פולינומיאלי. מכאן אפשר לגזור דרך אופרטיבית לפתור כל בעיה ב-NP בעזרת רדוקציה לבעיה שכבר פתרנו (וגם רדוקציות כאלו כבר ידוע איך לבנות בצורה מעשית). לכן מספיק לומר "שיטת ההצפנה הזו מתבססת על בעיה ב-NP" כדי שיהיה בטוח שאם נוכיח ש-P=NP בצורה קונסטרקטיבית, זה הסוף. |
|
|
|
|
|
|
||
|
||||
|
חוץ מהוכחה לא-קונסטרוקטיבית, עוד אפשרות שתציל את ההצפנות היא שהאלגוריתם שיימצא יהיה פולינומיאלי, אבל עם קבועים (חזקה אלף) שיהפכו אותו ללא מעשי עבור השימושים המעשיים בהצפנות. | |
|
|
|
|
|
||
|
||||
|
כולנו יודעים שלזהות הוכחה הרבה יותר קל מלחבר הוכחה. אם חלילה יתגלה ש-P=NP, העובדה הזו לא תשתנה. מה שישתנה תהיה המשמעות שאנו מעניקים להגדרה המתמטית של P: לא יהיה ניתן יותר לומר שהיא מכילה רק שפות קלות-להכרעה, ונצטרך לאפיין את המושג "קל לחישוב" בצורה יותר עדינה. |
|
|
|
|
|
|
||
|
||||
|
אני לא מבין למה זה נכון. כבר עכשיו P מכילה גם שפות שאפשר להכריע רק בזמן שהוא פולינום בחזקת גוגול (אני בטוח שאפשר להנדס כזו שפה, לא?), אז כבר עכשיו קשה להגיד שזה "קל להכרעה". | |
|
|
|
|
|
||
|
||||
|
נכון, הגזמתי לגבי המשמעות של P. היא מכילה גם הרבה דברים מאוד קשים להכרעה. אני אצטרך לחשוב על זה, כנראה ששוויון אינו בהכרח אסון.. | |
|
|
|
|
|
||
|
||||
|
הוא *עלול* להיות אסון למי שמשתמש בהצפנה (ה"עלול" מגיע מירדן). | |
|
|
|
|
|
||
|
||||
|
אולי אני מפספס משהו ממש בסיסי אבל אני לא משוכנע שזה נכון. אתה יכול לחשוב על הוכחה? נניח שהמודל שלנו הוא מכונת טיורינג (או כל מודל אחר שאתה מעדיף). | |
|
|
|
|
|
||
|
||||
|
אתה לא משוכנע שמה נכון? שקיימות בעיות שהפתרון שלהם הוא חזקה בגודל הזה? זו תוצאה של מה שמכונה Time hierarchy theorem. הבעיה היא שההוכחה של המשפט שאני מכיר היא לא קונסטרקטיבית - משתמשים שם בלכסון (די מגניב) ולכן אני לא יודע להנדס לך שפה שבאמת צריך פולינום ממעלה גוגול בשבילה. מכיוון שמשפט ההיררכייה הוא די כללי ומתייחס לא רק ל-P, אני נוטה לנחש שאפשר להנדס כזו שפה, אבל ייתכן מאוד שאני טועה. אולי ההוכחה שיש בויקיפדיה האנגלית כן קונסטרקטיבית: |
|
|
|
|
|
|
||
|
||||
|
אתה צודק. זכרתי שיש משפט היררכיה של המקום אבל לא משפט היררכיה (פולינומי) של הזמן. טעות שלי. | |
|
|
|
|
|
||
|
||||
|
עד כמה שאני מבין (למרות שאני קצת פחות סומך על עצמי כרגע) ההוכחה (שאני מכיר) היא כן קונסטרוקטיבית. מוכיחים ששפת כל המכונות M והקלטים x כך ש- M מקבלת את x בפחות מ- f(|x|) צעדים היא כריעה בזמן f^3 (נגיד) ולא כריעה בזמן f(n/2). לכן לכל n^k קל להראות שפה פולינומית שלא חשיבה ב- n^k. |
|
|
|
|
|
|
||
|
||||
|
מה של גוגול? אולי התכוונת לצ'כוב? | |
|
|
|
|
|
||
|
||||
|
"This article is about the large number. For the Internet company, see Google. For the author, see Gogol"
http://en.wikipedia.org/wiki/Googol |
|
|
|
|
|
|
||
|
||||
|
את הסופר אני לא מכיר, אבל מסתבר שיש קשר בין מנוע החיפוש לבין המספר בעל מאה האפסים. למעשה, השם Google מקורו כולו בעיוות שם המספר, שנעשה בטעות על ידי מפתחי המנוע. | |
|
|
|
|
|
||
|
||||
|
כן, זה אחד מפרטי הטריוויה הרבים על החברה הזו (ידעת שה-"Page rank" נקרא על שם פייג', אחד ממקימי החברה?). מצאתי את עצמי פעם אומר "גוגל" במקום "גוגול", למרבה המבוכה. אתה לא מכיר את גוגול או שלא קראת את גוגול? |
|
|
|
|
|
|
||
|
||||
|
לא מכיר, למרבה הבושה. | |
|
|
|
|
|
||
|
||||
|
בשביל זה יש ויקיפדיה (ותרגומים לעברית של ספרים שלו). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |