שתי הערות 468456
נטפקן מתחיל יום ו', 18/1/2008, 17:50
"שבע וחצי מיליוני שנים" - יותר עדיף "שבעה".

אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל).

אם אינני טועה, לא ידועות אפליקציות הצפנה המבוססות על בעיות NP. העניין הוא שבעיות NP קשות במקרה הגרוע, אבל לאו דווקא במקרה שנבחר אקראית.
שתי הערות 468464
גדי אלכסנדרוביץ' • בתשובה לנטפקן מתחיל יום ו', 18/1/2008, 18:46
מן הסתם RSA, דיפי-הלמן ודומיו מבוססים על בעיות שהן ב-NP (לא NP-שלמות) כך שקיימות אפליקציות כאלו. בוודאי שכך ש-P אינו שווה ל-NP לא אומר ששיטות שמבוססות על בעיה NP-קשה הופכות לבלתי ניתנות לפיצוח; זה רק מגביר את הקושי שאנחנו מייחסים להן.

(אפשר לנטפק עוד יותר אם רוצים ולומר ש-NP הוא רק בעיות הכרעה ומה הקשר בינו לבין חישובי הפונקציות של RSA ודיפי הלמן ושות')
שתי הערות 468501
נטפקן מתחיל • בתשובה לגדי אלכסנדרוביץ' יום ו', 18/1/2008, 23:00
מגיע לי עונש חמור על אי הדיוק שלי (נשרה לי המילה "שלמה" בנקודה קריטית). אני אנסה לנסח שוב את ניטפוקי:

מאמרך טוען ש: אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל)

אך לעניות דעתי (הענייה עד מאוד) אין אפליקציות הצפנה המבוססות על בעיות NP-שלמות (למרות שמחפשים).
שתי הערות 468510
גדי אלכסנדרוביץ' • בתשובה לנטפקן מתחיל יום ו', 18/1/2008, 23:47
אכן (עד כמה שידוע לי, כיוון מבטיח אחד הוא הצפנה שמבוססת על ה-Shortest Vector Problem ב-Lattices; זו בעיה NP-קשה לקירוב ברמת דיוק מסויימת, אבל בינתיים לא מכירים הצפנה שפיצוח שלה ידרוש דיוק שכזה אלא פחות מכך).

בכל מקרה, הקיום או אי הקיום כרגע של הצפנות שמבוססות על בעיות כאלו לא משנה את הנקודה העיקרית - שבעיות כאלו יכולות להיות שימושיות, וה"חשש" שיתגלה בהם פגם נמוך יותר, יחסית.
שתי הערות 468543
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 11:30
המשפט הנדון לא מבטא את המוטיבציה העיקרית לפתרון בעיית P/NP. לדעתי רוב העוסקים בתחום משערים שהוכחה ש- P שונה מ- NP לא תביא מיידית למציאת פונקציה חד-כיוונית (שהיא אבן הבניין הבסיסית להצפנה). לכן לדעתי היחס בין הצפנה לשאלת P/NP הוא בעיקר בכיוון השלילי: אם P=NP אין אפשרות להצפנה (קלאסית). אולי כדאי בכל זאת לחשוב על שינוי הניסוח במאמר כדי שמי שאין לו רקע בנושא לא יחשוב שפתרון P/NP יניב בהכרח הצפנה (או שזו המוטיבציה בחקר P/NP).

מלבד בעיות Lattice שציינת, היו נסיונות להתבסס על בעיית Subset-Sum (השלמה ב- NP) לצורך הצפנה. למיטב ידיעתי כל השיטות שהוצעו עד עתה התבססו על סוגים ספציפיים של קלטים ונמצאו עבורן שיטות פיצוח.
שתי הערות 468547
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני שבת, 19/1/2008, 11:47
לא ניסיתי לומר שהמשפט הנדון מבטא את המוטיבציה העיקרית... לדעתי המוטיבציה העיקרית (בהינתן שאכן P שונה מ-NP, כי ההפך הוא סנסציה ומכת מוות לקריפטוגרפיה הא-סימטרית הקיימת) היא תיאורטית, בדומה למוטיבציה להוכיח את משפט פרמה.
שתי הערות 468555
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 12:16
מעולה אז כולנו מסכימים. העניין הוא שהנטפקן חשב (ואני מסכים) שממה שכתוב עלולים להשתמע הדברים ה(אולי) לא נכונים האלה.

אגב - לא רק הצפנה אסימטרית אלא כל הצפנה (קלאסית) שמבוססת על קושי חישובי (כלומר הכל חוץ ממפתחות חד פעמיים) נמצאת ב- NP.

ועוד הבהרה לתגובה שלי שמעלייך: המשפט האחרון שלי (על חוסר הצלחה לייצר הצפנה בטוחה) מתייחס ל- Subset-Sum בלבד. יש הרבה הצפנות מבוססות Lattice שנחשבות בטוחות.
שתי הערות 469088
צפנת פענח • בתשובה להאייל האלמוני יום ד', 23/1/2008, 5:36
(1) קימות סכמות הצפנה (סימטריות) המבוססות על הקושי של subset-sum שלא נשברו. ראה למשל:
יחד עם זאת, הסכימה הנ"ל מבוססת על הקושי של הבעיה בטווח של פרמטרים בהם היא אינה ידועה להיות NP-שלמה.

(2) ביסוס קריפטוגרפיה על NP-שלמות היא אחת הבעיות החשובות ביותר בתיאוריה של קריפטוגרפיה.
שתי הערות 469104
האייל האלמוני • בתשובה לצפנת פענח יום ד', 23/1/2008, 11:15
נקודה 2 - בהחלט (השתמע אחרת מתגובתי?). כתבתי שהפרדת P/NP לא תביא מיידית לביסוס קריפטוגרפיה על NP שלמות. ניתן לשער אפילו ששתי הבעיות (הפרדת P/NP וביסוס הצפנה על NPC) הן "בלתי תלויות" במובן מסוים (אבל אי אפשר לדעת).

מלבד זאת, מספר תוצאות שליליות (למשל http://portal.acm.org/citation.cfm?id=1132516.113261...) מצביעות על כך שפונקציה חד כיוונית המבוססת על NP-שלמות צריכה לקיים כמה תנאים מאוד מיוחדים.
שתי הערות 468512
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 0:10
האם קיים פתרון בסיבוכיות ידועה עבור אחת (ומכאן כל) הבעיות הNP-שלמות ?
שתי הערות 468514
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני שבת, 19/1/2008, 0:21
בוודאי; למשל, עבור SAT (שהשאלה בה היא "האם פסוק לוגי בתחשיב הפסוקים הוא ספיק?") פתרון פשוט הוא "בדוק את כל ההשמות בזו אחר זו; אם אחת סיפקה את הפסוק, ענה "כן", אחרת ענה "לא"".

הבעיה בפתרון הזה היא שמספר ההשמות הוא אקספוננציאלי באורך הפסוק - כלומר, הסיבוכיות של הפתרון גבוהה מדי מכדי שהוא ייחשב מעשי.
שתי הערות 468515
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 0:36
אבל המשמעות של זה היא שכל בעיה שניתן לוודא את הפתרון שלה באופן פולינומי, ניתן לפתור באופן אקספוננציאלי.
זה יכול להיות מאוד שימושי עבור בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט.
שתי הערות 468525
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני שבת, 19/1/2008, 8:13
אתה בהחלט צודק - זו אכן המשמעות של כך.

אני לא מכיר בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט ועם זאת פתרון שלהן ניתן לבדיקה פולינומית. מכיוון ש"בצע רדוקציה ל-SAT ובדוק את כל ההצבות) הוא פתרון נאיבי למדי (במובן זה שאין בו שום דבר מחוכם מעבר לקופסה השחורה של הרדוקציה), קח בחשבון ש"הפתרון הרגיל" מוגדר בהתאם.
שתי הערות 468544
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 11:38
אפשר גם לומר שכיוון שלפי ההגדרה לכל בעיה ב- NP יש הוכחה באורך פולינומי שאפשר לבדוק בזמן פולינומי, אפשר פשוט לבדוק את כל המחרוזות באורך המתאים ולראות אם הן מהוות הוכחה וזה ייתן פתרון בזמן אקספוננציאלי (כשהמעריך הוא פולינום באורך הקלט).

לא ידוע (וכנראה שלא נכון) שכל בעיה ב- NP ניתנת לפתרון בזמן אקספוננציאלי עם מעריך ליניארי באורך הקלט.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות