 |
עניין של זמן | 2828 |  |
||||||||
 |
|
 |
|||||||||
 |
 |
פרסומים אחרונים במדור "מדע"
|
| הצג את כל התגובות | הסתר את כל התגובות |
|
|
 |
||
|
||||
|
זה אלגוריתם שמוכן לקבל כל קלט שהוא? אז אי אפשר לחזות כמה זמן ידרש לו לפתור בעיה. או אולי זה אלגוריתם שמקבל כל קלט כאילו זה הפיתרון? אז זמן הריצה שלו הוא זמן קליטת הקלט. יכול גם שזמן הביצוע שלו זה אפס כי תוכן הקלט לא חשוב וצריך רק לדעת מי הזין את המחשב הנאיבי. הסבר נא. |
|
|
 |
|
|
|
||
|
||||
|
''אלגוריתם מיון נאיבי'', לצורך העניין, הוא שם כללי לקבוצה של כמה אלגוריתמים שאינם מתבססים על שום רעיון מחוכם, אלא על תפיסה אינטואיטיבית יחסית של מיון. למשל, מיון הכנסה, שהוא נפוץ למדי בקרב מי שמשחק קלפים - תתחיל עם יד ריקה, קח קלף מהערימה. קח את הקלף הבא והכנס אותו למקומו הנכון (לפני או אחרי הקלף הקיים). קח עוד קלף והכנס אותו למקומו הנכון (על ידי השוואה עם שני הקלפים שכבר יש ביד) וכן הלאה. במקרה ה''גרוע'', כל קלף יושווה עם כל הקלפים האחרים, ולכן מספר ההשוואות יהיה פרופורציוני לריבוע מספר הקלפים. שים לב שוב לנקודה המרכזית כאן - מדידת הזמן היא לא אבסולוטית (כמה שניות, למשל) אלא מתמקדת בקצב הגידול של ''זמן הריצה'' כאשר מגדילים את הקלט (כאן ''זמן הריצה'' הוא בעצם ''מספר הפעולות הבסיסיות''). |
|
|
|
|
|
|
||
|
||||
|
נדמה לי שהאלמוני פשוט לא הבין את המלה "מיון", ואכן זו מלה שדורשת הסבר כשקהל היעד לא למד מדעי המחשב: לרוב חושבים על "מיון" כחלוקת קבוצה לתת-קבוצות לפי קריטריון1, ואז מתבקש ש"אלגוריתם מיון" פירושו אלגוריתם הכרעה. כנראה מוטב לומר "אלגוריתמי סידור". (לאלמוני - אם זה הבלבול, ואם הוא עדיין קיים - הכוונה ב"מיון" לסידור קבוצת מספרים, שנתנונים ללא סדר, לפי גודלם.) 1 זו אפילו האטימולוגיה של המלה. |
|
|
|
|
|
|
||
|
||||
|
המממ, אכן. לא חשבתי על זה בכלל. | |
|
|
|
|
|
||
|
||||
|
נא להסביר את (1)! | |
|
|
|
|
|
||
|
||||
|
''מיון'' נולד מהמילה ''מין''. יענו, מיון היה במקור חלוקת איברים לתת-קבוצות לפי מינם. | |
|
|
|
|
|
||
|
||||
|
ומה ההבדל בין זה לבין המובן הרגיל של מיון? | |
|
|
|
|
|
||
|
||||
|
זה (חלוקה על-פי מינים) המובן ה"רגיל" של מיון. המובן השונה הוא זה של מדעי-המחשב – סידור לפי סדר כלשהו (למשל, לקסיקוגרפי). שימוש במשמעות רגילה: למיין את הקלפים לזוגיים ואי-זוגיים. שימוש במשמעות ממ"ח: למיין את הקלפים בסדר עולה. |
|
|
|
|
|
|
||
|
||||
|
לדעתי מדובר בטעות תרגום שמישהו עשה אי שם בשנות הששים, ומאז אנו תקועים עם מושגים עבריים לא מדוייקים. המילים "SORT" או "ORDER" הן הן שהיו צריכות להיות מתורגמות ל"סידור" (אגב: סידור בשני מובניו - גם כסדור של פרטים לפי גודלם, וגם סידור במובן של "לסדר את העניינים": sort things out) - בעוד ש"מיון" היא המילה שהיתה צריכה להיות התרגום ל- "filtering" או "selecting" מעולם המחשבים. |
|
|
|
|
|
|
||
|
||||
|
sort באנגלית זה מין/סוג/מחלקה. to sort זה לארגן לפי מין/סוג/מחלקה. התרגום למיון הוא דווקא מצויין. המילה order במדעי המחשב אכן מתורגמת למילה סדר (למיטב ידיעתי). |
|
|
|
|
|
|
||
|
||||
|
באופן כללי, אומרים על אלגוריתם שהוא "נאיבי" אם הוא "לא מתוחכם", כלומר, הוא פותר את הבעיה בצורה הכי פשוטה שאפשר לחשוב עליה. במקרה של אלגוריתמי מיון, אלגוריתם נאיבי לדוגמא הוא האלגוריתם שהרבה אנשים משתמשים בו למיון הקלפים שלהם במשחקי קלפים: בכל פעם, תפוס אחד מהקלפים והעבר אותו למקומו הנכון, והמשך כך עד שהקלפים ממוינים. כדי למיין n קלפים, האלגוריתם הזה יבצע בערך n בריבוע צעדים. הסיבה שעבור כל קלף, צריך לבצע בערך n צעדים כדי להעביר למצוא את מקומו הנכון, ואת זה צריך לבצע עבור n קלפים. |
|
|
|
|
|
|
||
|
||||
|
"שבע וחצי מיליוני שנים" - יותר עדיף "שבעה". אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל). אם אינני טועה, לא ידועות אפליקציות הצפנה המבוססות על בעיות NP. העניין הוא שבעיות NP קשות במקרה הגרוע, אבל לאו דווקא במקרה שנבחר אקראית. |
|
|
|
|
|
|
||
|
||||
|
מן הסתם RSA, דיפי-הלמן ודומיו מבוססים על בעיות שהן ב-NP (לא NP-שלמות) כך שקיימות אפליקציות כאלו. בוודאי שכך ש-P אינו שווה ל-NP לא אומר ששיטות שמבוססות על בעיה NP-קשה הופכות לבלתי ניתנות לפיצוח; זה רק מגביר את הקושי שאנחנו מייחסים להן. (אפשר לנטפק עוד יותר אם רוצים ולומר ש-NP הוא רק בעיות הכרעה ומה הקשר בינו לבין חישובי הפונקציות של RSA ודיפי הלמן ושות') |
|
|
|
|
|
|
||
|
||||
|
מגיע לי עונש חמור על אי הדיוק שלי (נשרה לי המילה "שלמה" בנקודה קריטית). אני אנסה לנסח שוב את ניטפוקי: מאמרך טוען ש: אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל) אך לעניות דעתי (הענייה עד מאוד) אין אפליקציות הצפנה המבוססות על בעיות NP-שלמות (למרות שמחפשים). |
|
|
|
|
|
|
||
|
||||
|
אכן (עד כמה שידוע לי, כיוון מבטיח אחד הוא הצפנה שמבוססת על ה-Shortest Vector Problem ב-Lattices; זו בעיה NP-קשה לקירוב ברמת דיוק מסויימת, אבל בינתיים לא מכירים הצפנה שפיצוח שלה ידרוש דיוק שכזה אלא פחות מכך). בכל מקרה, הקיום או אי הקיום כרגע של הצפנות שמבוססות על בעיות כאלו לא משנה את הנקודה העיקרית - שבעיות כאלו יכולות להיות שימושיות, וה"חשש" שיתגלה בהם פגם נמוך יותר, יחסית. |
|
|
|
|
|
|
||
|
||||
|
המשפט הנדון לא מבטא את המוטיבציה העיקרית לפתרון בעיית P/NP. לדעתי רוב העוסקים בתחום משערים שהוכחה ש- P שונה מ- NP לא תביא מיידית למציאת פונקציה חד-כיוונית (שהיא אבן הבניין הבסיסית להצפנה). לכן לדעתי היחס בין הצפנה לשאלת P/NP הוא בעיקר בכיוון השלילי: אם P=NP אין אפשרות להצפנה (קלאסית). אולי כדאי בכל זאת לחשוב על שינוי הניסוח במאמר כדי שמי שאין לו רקע בנושא לא יחשוב שפתרון P/NP יניב בהכרח הצפנה (או שזו המוטיבציה בחקר P/NP). מלבד בעיות Lattice שציינת, היו נסיונות להתבסס על בעיית Subset-Sum (השלמה ב- NP) לצורך הצפנה. למיטב ידיעתי כל השיטות שהוצעו עד עתה התבססו על סוגים ספציפיים של קלטים ונמצאו עבורן שיטות פיצוח. |
|
|
|
|
|
|
||
|
||||
|
לא ניסיתי לומר שהמשפט הנדון מבטא את המוטיבציה העיקרית... לדעתי המוטיבציה העיקרית (בהינתן שאכן P שונה מ-NP, כי ההפך הוא סנסציה ומכת מוות לקריפטוגרפיה הא-סימטרית הקיימת) היא תיאורטית, בדומה למוטיבציה להוכיח את משפט פרמה. | |
|
|
|
|
|
||
|
||||
|
מעולה אז כולנו מסכימים. העניין הוא שהנטפקן חשב (ואני מסכים) שממה שכתוב עלולים להשתמע הדברים ה(אולי) לא נכונים האלה. אגב - לא רק הצפנה אסימטרית אלא כל הצפנה (קלאסית) שמבוססת על קושי חישובי (כלומר הכל חוץ ממפתחות חד פעמיים) נמצאת ב- NP. ועוד הבהרה לתגובה שלי שמעלייך: המשפט האחרון שלי (על חוסר הצלחה לייצר הצפנה בטוחה) מתייחס ל- Subset-Sum בלבד. יש הרבה הצפנות מבוססות Lattice שנחשבות בטוחות. |
|
|
|
|
|
|
||
|
||||
|
(1) קימות סכמות הצפנה (סימטריות) המבוססות על הקושי של subset-sum שלא נשברו. ראה למשל: יחד עם זאת, הסכימה הנ"ל מבוססת על הקושי של הבעיה בטווח של פרמטרים בהם היא אינה ידועה להיות NP-שלמה. (2) ביסוס קריפטוגרפיה על NP-שלמות היא אחת הבעיות החשובות ביותר בתיאוריה של קריפטוגרפיה. |
|
|
|
|
|
|
||
|
||||
|
נקודה 2 - בהחלט (השתמע אחרת מתגובתי?). כתבתי שהפרדת P/NP לא תביא מיידית לביסוס קריפטוגרפיה על NP שלמות. ניתן לשער אפילו ששתי הבעיות (הפרדת P/NP וביסוס הצפנה על NPC) הן "בלתי תלויות" במובן מסוים (אבל אי אפשר לדעת). מלבד זאת, מספר תוצאות שליליות (למשל http://portal.acm.org/citation.cfm?id=1132516.113261...) מצביעות על כך שפונקציה חד כיוונית המבוססת על NP-שלמות צריכה לקיים כמה תנאים מאוד מיוחדים. |
|
|
|
|
|
|
||
|
||||
|
האם קיים פתרון בסיבוכיות ידועה עבור אחת (ומכאן כל) הבעיות הNP-שלמות ? | |
|
|
|
|
|
||
|
||||
|
בוודאי; למשל, עבור SAT (שהשאלה בה היא "האם פסוק לוגי בתחשיב הפסוקים הוא ספיק?") פתרון פשוט הוא "בדוק את כל ההשמות בזו אחר זו; אם אחת סיפקה את הפסוק, ענה "כן", אחרת ענה "לא"". הבעיה בפתרון הזה היא שמספר ההשמות הוא אקספוננציאלי באורך הפסוק - כלומר, הסיבוכיות של הפתרון גבוהה מדי מכדי שהוא ייחשב מעשי. |
|
|
|
|
|
|
||
|
||||
|
אבל המשמעות של זה היא שכל בעיה שניתן לוודא את הפתרון שלה באופן פולינומי, ניתן לפתור באופן אקספוננציאלי. זה יכול להיות מאוד שימושי עבור בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט. |
|
|
|
|
|
|
||
|
||||
|
אתה בהחלט צודק - זו אכן המשמעות של כך. אני לא מכיר בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט ועם זאת פתרון שלהן ניתן לבדיקה פולינומית. מכיוון ש"בצע רדוקציה ל-SAT ובדוק את כל ההצבות) הוא פתרון נאיבי למדי (במובן זה שאין בו שום דבר מחוכם מעבר לקופסה השחורה של הרדוקציה), קח בחשבון ש"הפתרון הרגיל" מוגדר בהתאם. |
|
|
|
|
|
|
||
|
||||
|
אפשר גם לומר שכיוון שלפי ההגדרה לכל בעיה ב- NP יש הוכחה באורך פולינומי שאפשר לבדוק בזמן פולינומי, אפשר פשוט לבדוק את כל המחרוזות באורך המתאים ולראות אם הן מהוות הוכחה וזה ייתן פתרון בזמן אקספוננציאלי (כשהמעריך הוא פולינום באורך הקלט). לא ידוע (וכנראה שלא נכון) שכל בעיה ב- NP ניתנת לפתרון בזמן אקספוננציאלי עם מעריך ליניארי באורך הקלט. |
|
|
|
|
|
|
||
|
||||
|
ככל שעובר הזמן מהירויות המחשבים מגיעות למהירויות גבוהות יותר, ולכן מה שנראה כבלתי פתיר בזמן שאורכו כרגע הוא אורך ימי היקום יהיה פתיר בעוד כמה שנים. לא?! | |
|
|
|
|
|
||
|
||||
|
לא. זה בדיוק מה שניסיתי לומר במאמר. בפרט, אולי משהו שהיום היה בלתי אפשרי ביותר מחר יהיה פתיר, אבל משהו דומה לו, שהוא רק ''טיפה'' יותר מסובך, עדיין יהיה בלתי פתיר, וכן הלאה. |
|
|
|
|
|
|
||
|
||||
|
אז מה מצפה לנו בערך במאמר הבא? | |
|
|
|
|
|
||
|
||||
|
אין לי מושג. רוצה להציע משהו? | |
|
|
|
|
|
||
|
||||
|
עוד שאלה: אם קיים מאגר של מספרים ראשוניים וגורמיהם, שמהירות הגישה שלו קצרה למדי. נניח שבכל הכנסה של גורם ראשוני, מהירות הגישה לנתונים היא פחות ממספר שניות, כך שכל פעם שניגשים למאגר מספר השניות שצריך להמתין לקבלת תשובה הוא נמוך, אז אפשר לשבור את ה-RSA כי אין צורך לחשב אלא רק לעשות פעולת קלט-פלט בסיסית. מה דעתך? |
|
|
|
|
|
|
||
|
||||
|
ב-RSA בימינו (בפעם האחרונה שבדקתי) עובדים עם מספרים בני 2048 סיביות. אז נניח 1024 סיביות למספר ראשוני (כי המספרים של RSA הם מכפלה של שני ראשוניים). זה נותן לנו מספר של 300 ספרות בערך. אין לי מושג כמה ראשוניים בני 300 ספרות יש, אבל עד כמה שהבנתי אפשר להעריך אותם (בעזרת "משפט המספרים הראשוניים") ולקבל שבערך אחד ל-700 מספרים בתחום הזה יהיה ראשוני (יותר במדוייק - אחד ל-ln גודל המספרים בתחום יהיה ראשוני). אם נתעסק רק במספרים שהם בערך בני 300 ספרות (כלומר, נוריד מהם את כל המספרים שהם בני 299 ספרות) יוצא שאנחנו מדברים על קבוצה של משהו כמו 9 כפול 10 בחזקת 299 מספרים. תחלק את זה ב-700 ותקבל שעדיין יש, ובכן, *המון* מספרים ראשוניים בני 300 ספרות בערך. כמה המון? יותר מכפי שכל האטומים ביקום יוכלו לאחסן גם אם כל אטום משמש לאיחסון של זיליארד ראשוניים. עכשיו מתבקש לבוא מתמטיקאי ולהצביע על כל הטעויות ב"ניתוח" שלי (אבל נראה לי שהמסקנה הסופית נכונה). |
|
|
|
|
|
|
||
|
||||
|
אתה מתכוון לכך שכל המספרים הפריקים מחושבים במהירות גבוהה בגלל התקדמות המחשבים, וכתוצאה מכך מספרים בעלי מספר סיביות רבות יותר מופיעים בחישוב. השאלה הבאה שלי היא: האם ניתן להחזיק הרבה קשרי תקשורת בין מחשבים, כי ככל שמספר הסיביות גדול כך יש גבול לכמות קשרי תקשורת בין מחשבים. כיצד ארגון כמו צבא יכול להתמודד עם דבר כזה? אולי באלגוריתם של CSMA/CD או משהו כזה? | |
|
|
|
|
|
||
|
||||
|
אין לי מושג מה זה CSMA/CD, אבל אני לא בטוח שהבנתי מה הבעיה. 2048 סיביות זה 256 בייטים; אלו "גרושים" מבחינת תקשורת ומקום אכסון בימינו. גם אם תכפיל את זה פי אלף, תקבל גודל אפסי (ותגדיל את הבטיחות בהרבה יותר מאשר פי אלף), כך שהגודל הוא לא הבעיה. יש כמובן בעיות אחרות שמערבות מפתחות פומביים; בפרט, העובדה שצריך להיות משוכנעים שמפתח פומבי של מישהו הוא אכן "שלו" (מתגברים על זה באמצעות מנגנון שנקרא Certificates; אבל הוא רחוק מלהיות משביע רצון), והעובדה שהצפנה בעזרת מפתח פומבי היא איטית יחסית (ולכן לרוב משתמשים במפתח פומבי על מנת לבצע החלפה של מפתחות זמניים, שבהם משתמשים עבור הצפנה סימטרית מהירה). |
|
|
|
|
|
|
||
|
||||
|
זה לא מה שהוא התכוון. אתה מציע - אם אני מבין נכון - להחזיק מאגר מאוד גדול של מספרים פריקים והגורמים להם, וכך בהנתן מספר אפשר פשוט לשלוף את הגורמים. ובכן, אם המספר שאנו רוצים לפרק הוא בן 1024 סיביות, אז שני המספרים הראשוניים הם בני 512 סיביות. כמה מספרים ראשוניים בני 512 סיביות יש? בערך 2 בחזקת 256 חלקי 200. שזה בערך 2 בחזקת 248 (אני הולך לקראתך). זה המון. 2 בחזקת 40 זה טרה, אז מה שיש פה זה טרה של טרה של טרה של טרה של טרה של טרהבייט של מידע. אי אפשר להחזיק מאגר כזה גדול. טזה רק מאגר של הגורמים הראשוניים! אם תרצה להחזיק מאגר של מכפלות של גורמים ראשוניים, זה ייקח לך בריבוע. בקיצור, זה בלתי אפשרי. וגם אם תצליח, מאגר למספרים של 2048 סיביות, שהוא לא קשה וקיים כיום, ידרושה ממך לעשות פי 2 בחזקת 1024 עבודה. שזה, עוד פעם, המון. |
|
|
|
|
|
|
||
|
||||
|
אגב, השאלה לא מנוסחת הכי טוב - אין למספרים ראשוניים גורמים פרט להם עצמם ול-1. אני מניח שהכוונה הייתה למספרים שהם מכפלת שני ראשוניים (וכאלו יש הרבה יותר מאשר ראשוניים). | |
|
|
|
|
|
||
|
||||
|
אותך לקנטור. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
עד כמה מותר לי לשחק עם החוקים שמגדירים בעיה ? למשל איפה הכשל בבעיה הבאה : נתונה סדרה של דיסקיות מסודרות לפי רוחבן בערמה (בדומה למגדל האנוי) כאשר לאחת הדיסקיות עיגול אדום קטן בצד הפונה מעלה. המטרה היא למצא את הדיסקית הסוררת, מה שניתן לראות רק כאשר היא עליונה. אך במקום שלושה מוטות, מצויים בפניך שני סטים של שלושה מוטות, כאשר אתה מחלק את ערמת הדיסקיות לשני חלקים היכן שתרצה, מניח כל חצי על מוט אחר ומכאן כל סט של שלושה מוטות מתנהג כמגדל האנוי נפרד לכל דבר. הפתרון הפשוט הוא לחלק את הערמה באמצע ואז לשחק בסט אחד ולאחר מכן בשני, הסיבוכיות היא ((O(2^(n/2 כמדומני. אך אם ידוע לך באיזו דיסקית מדובר, הרי עצם חלוקה נכונה תפתור את הבעיה מייד. אני מניח שעצם היות הבעיה דו-שלבית (ולכן "מלאכותית" במובן מסויים) תצרום, שכן האפשרות לוודא את נכונות הפתרון היא חד פעמית, אבל האם יש סט של חוקים המגדיר מה מותר ואסור בהגדרת בעיה ? |
|
|
|
|
|
|
||
|
||||
|
מדידת הסיבוכיות היא בד''כ על פי המקרה הגרוע ביותר מבין אלו שהאלגוריתם אמור לפעול עליהם. כלומר, אם אתה יודע תמיד איפה הדיסקית, בוודאי שהסיבוכיות של כל העניין טריוויאלי - וגם הבעיה טריוויאלית. אם לעומת זאת הדיסקית יכולה להיות בכל מקום והאלגוריתם לא יודע איזה, אז לצורך בדיקת המקרה הגרוע ביותר אפשר להניח שיש ''יריב ערמומי'' שרואה את הפתרון שלך, ושם דיסקית במקום שיגרום הכי הרבה ''נזק''. | |
|
|
|
|
|
||
|
||||
|
אז לא מחשיבים את Quicksort כאלגוריתם שפועל ב nlonn יותר? | |
|
|
|
|
|
||
|
||||
|
לא החשיבו אותו כך אף פעם, כשמדברים על המקרה הגרוע. לכן לעתים קרובות מלמדים אותו בד בבד עם ניתוחי סיבוכיות על פי המקרה הממוצע. | |
|
|
|
|
|
||
|
||||
|
רק במקרה הממוצע (או אם משתמשים באלגוריתם ליניארי למציאת חציון כדי למצוא את הפיבוט). | |
|
|
|
|
|
||
|
||||
|
כמובן. הבעיה היא לא בP כי אין לאלגוריתם דטרמיניסטי דרך לפתור אותה בזמן פולינומי (נובע מההוכחה על האנוי), אבל בהינתן הפתרון, וידוא שלו (רק במהלך הראשון) כן נעשה בזמן פולינומי, לכן היא בNP, מה שהיה מפריך את P=NP אם הבעיה היתה תקפה. השאלה שלי היא למה בדיוק הבעיה לא תקפה ? |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח מה הכוונה ב"לא תקפה". על כל פנים, שים לב שיש כמה הבדלים מהותיים בינה לבין בעיות חישוביות "רגילות" - בפרט, זו בעיה של חיפוש, לא של תשובת "כן/לא", אבל בעיקר (וזה ההבדל המהותי) - היא מבוססת על קלט *חלקי*, שיש בו מידע מוסתר - בעצם, מעין "קופסה שחורה" שצריך להתמודד איתו. הכוונה היא שיכולים להיות שני קלטים שנראים זהה למכונה, ובכל זאת "מתנהגים" שונה (על סמך מהי הדיסקית המסומנת). נראה לי שכאן נמצא ההבדל המרכזי. | |
|
|
|
|
|
||
|
||||
|
"בעיה" היא פשוט פונקציה בינארית במשתנה אחד. יש לה קלט שהוא מחרוזת בינארית כלשהי ולכל קלט יש פלט מתאים (במקרה שלנו הפלט יכול להיות "1" או "0"). אפשר לחשוב על זה כטבלת אמת אינסופית שמתאימה ערך לוגי לכל מחרוזת. פתרון של הבעיה הוא פשוט תוכנה (או "מכונת טיורינג") שמחשבת את הפונקציה הזו. אתה בטח רואה שהניסוח שלך לא עונה לדרישה: אתה לא יכול להגדיר את המשחק שתיארת כפונקציה שהקלט שלה מגדיר באופן יחיד את הפלט (כפי שגדי ציין, על אותו קלט התחלתי יכולים להיות הרבה פלטים שונים). בדרך כלל ב"פתרון בעיות" או "חישוב" הגיוני לדרוש לדעת מה הבעיה לפני שמתחילים לפתור אותה אבל לפעמים העולם לא עובד כך. למשל אני עומד בתחנת אוטובוס ולא יודע מתי האוטובוס יגיע (אם בכלל), כמה כדאי לי לחכות לפני שאני מתיאש והולך ברגל? אלגוריתמי אונליין, למשל, מטפלים בסוג כזה של בעיות. אגב, באופן שקול אפשר להגדיר בעיה כתת-קבוצה של קבוצת המחרוזות (תת-הקבוצה המכילה את כל המחרוזות שהפלט עליהן הוא "1"). במקרה זה, תפקיד המכונה שלך לבדוק האם הקלט שייך לתת-הקבוצה או לא. |
|
|
|
|
|
|
||
|
||||
|
תודה לך ולגדי. הסבה לפונקציה בינארית היא טריוויאלית (האם קיימת דיסקית אדומה ?), לגבי היות הקלט סמוי, מותר לי להשתמש בקלט כדי למפות לתחום בשדה המספרים ? למשל בהינתן קלט A, האם קיים פתרון למשוואה דיופונטית מסויימת* בטווח המספרים עד e^A? בהינתן הפתרונות ניתן לבדוק זאת בזמן סביר (כלומר הבעיה בNP) אבל הוכח שאין נוסחה למציאת הפתרון למשוואה (וגם לא ניתן להוכיח שאין לה פתרון). גם אם קיים אלגוריתם למציאת הפתרון שמאפשר לעבור רק על שבריר מהמספרים, ניתן להגדיל את התחום כך שמספר המספרים עליהם יש לעבור יגדל מהר מספיק כדי שלא יהיה פתרון פולינומי. נ.ב. כשאני חורג לתחום הטרחנות הכפייתית אנא הודיעו לי ואני אעבור לדיון המתאים :) *אחת שעונה להגדרות של העדר יכולת למצא פתרון בצורה ישירה. |
|
|
|
|
|
|
||
|
||||
|
צריך להיזהר כאן. משוואות דיופנטיות שייכות ל-RE; כלומר, אם יש למשוואה פתרון, אפשר יהיה למצא אותו, *תמיד*. הבעיה היא רק עם זיהוי משוואות ללא פתרון. לכן להגיד "אין נוסחה למציאת הפתרון" זה לא מדוייק. אבל פרט לכך, אם אתה רוצה לנסות להוכיח פה משהו, תצטרך לתת הגדרות מדוייקות - מה הקלט, מה הרדוקציה, מה התחום וכו'. ייתכן שיתגלה פתאום שלא קל אפילו לבדוק את הפתרונות (כי הם גדולים מדי) או שההמרה למשוואות לוקחת זמן רב מדי, וכדומה. ואחרי זה, גם תצטרך להוכיח שלא קיים שום אלגוריתם שפותר את הבעיה ביעילות (זה שונה מאוד מ"מספר המספרים עליהם יש לעבור גדול" - אולי יש אלגוריתם שלא צריך לעבור על כל המספרים? צריך להוכיח שלא יכול להתקיים כזה). |
|
|
|
|
|
|
||
|
||||
|
לקלט מותר לייצג מה שאתה רוצה. כל עוד "טבלת האמת האינסופית" מוגדרת היטב, זה חוקי. אני לא יכול להגיד שאני מבין גדול (או קטן) במשוואות דיופנטיות אבל יש מספר נקודות עדינות שיש לתת עליהן את הדעת: 1. "בהינתן הפתרונות ניתן לבדוק זאת" - אם הקלט הוא A ואתה מרשה פתרונות אקספוננציאלים ב- A אתה בבעיה. בהגדרה של NP אורך ההוכחה חייב להיות פולינומי באורך הקלט. 2. אי קיום נוסחה לא אומר שאין אלגוריתם לפתרון הבעיה. אין נוסחה לפונקציה קדומה של (exp(-x^2 ובכל זאת אפשר לחשב ערך של פונקציה קדומה כזו (עם תנאי שפה מסוימים) בכל נקודה בכל דיוק. 3. גם אם אי אפשר להוכיח שאין לבעיה פתרון, זה לא אומר שאי אפשר להראות שאין לה פתרון בתחום מוגבל (למעשה בטוח שאפשר, השאלה בכמה זמן). עדיין לא הבנתי מה הדוגמא שלך אמורה להראות, בעיה ב- NP שאינה ב- P? אם כן, שים לב שדי קשה להוכיח שבעיה (כריעה) כלשהי אינה ב- P. |
|
|
|
|
|
|
||
|
||||
|
גם אתה וגם גדי מצאתם חורים בטענה, שנבעו בין היתר מהסתמכות על מקור מפוקפק בשם ויקיפדיה העברית, שם נכתב "לחלק מהמשוואות הדיופנטיות, לא קיימת דרך ישירה למציאת הפתרונות, חוץ מבדיקת כל האפשרויות...", אני מניח שמשפט זה לא הוכח כראוי ? אם אכן נדרש מעבר על כל הפתרונות, בלי קשר לקושי לבדוק פתרון יחיד, כמות הפתרונות מוציאה את הבעיה מתחום הפולינומי. דווקא 1 לא נראה לי כמכשול, כי אם אני מרשה מספרים עד e^A, מספר הספרות יגיע עד ~ln(e^A)~A ולכן הכפלה וחיבור של מספר כזה של סיביות יהיה פולינומי בA. דווקא להראות שהבעיה אינה בP נדמה לי שהצלחתי (אם קיים אלגוריתם חיפוש פתרונות ביעילות f(n), אני מגדיל את הטווח לF(n) כשf(F(n)=e^A)), הבעיה שאז וידוא הפתרון (כפי שציין גדי) אינו פולינומי. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שהם מתכוונים שלא ידועה דרך אחרת למציאת הפתרונות ולא שלא יכולה להתקיים כזו. לגבי האורך - אתה צריך להיות פולינומי באורך הקלט ולא בערכו. אפשר להגדיל מלאכותית את אורך הקלט אבל אז גם לאלגוריתם מותר לרוץ בזמן יותר ארוך (ואז הבעיה יכולה אפילו להפוך להיות ב- P). לגבי הטענה האחרונה שלך, מי אמר שכדי לבדוק אם יש פתרון בתחום (סופי) מסוים צריך "אלגוריתם חיפוש פתרונות"? יכול להיות שיש שיטה הרבה יותר פשוטה שאף אחד עוד לא גילה. בכל מקרה ברגע שאתה מפסיק להיות פולינומי באורך הקלט כבר לא ברור אם הבעיה ב- NP. |
|
|
|
|
|
|
||
|
||||
|
הקלט הוא A, המרחב בו מחפשים פתרונות גדול יותר, אבל זה לא קשור לקלט אם הבנתי נכון. וידוא הפתרון הוא אכן פולינומי בA, כי המספר המקסימלי שתאלץ לבדוק הוא e^A, עליו תאלץ לבצע פעולות כפל וחיבור. מספר הסיביות במספר פרופורציונלי לA ולכן פעולות כמו כפל וחיבור יהיו פולינומיות בA. אם יש לך אלגוריתם שמוצא פתרון (אם יש) עבור תחום קטן מn בלי הגבלה על גודלו של n ובזמן שלא תלוי בn, אז אתה יכול להשאיף את n לאינסוף ולדעת האם יש או אין פתרון למשוואה, בסתירה למה שבר הוכח. |
|
|
|
|
|
|
||
|
||||
|
אני אדם פשוט, וגם ריבוי האלמונים לא עוזר לי - בהנחה שאתה מי שהתחיל את הדיון הזה, תוכל לכתוב הודעה מסודרת שבה אתה מסביר, מההתחלה ועד הסוף, מה בדיוק אתה מנסה להוכיח כאן? | |
|
|
|
|
|
||
|
||||
|
ההודעות האחרונות היו סתם טרחנות בנוגע לנקודת הכשל. לא הצלחתי להוכיח דבר, לכן אחסוך את זמנך. | |
|
|
|
|
|
||
|
||||
|
טרחנות זו בטח לא, והגישה שלך דווקא סיקרנה אותי. | |
|
|
|
|
|
||
|
||||
|
הרעיון היה לנצל את העובדה שמספר בן A סיביות נמצא בטווח מספרים בן שתים בחזקת A סיביות. כלומר אם תהיה לי שאלה שאפשר לוודא את הנכונות שלה בזמן פולינומי(NP), אבל אין דרך למצא את הפתרון שלה (כמובן הכל בשלמים, או לכל הפחות בקבוצה לא צפופה, אם כי גם כאן בטח יש הסתייגויות שאני לא מכיר), אני אוכל באמצעות הקלט להגדיר טווח מספרים גדול מספיק כדי שזמן מציאת הפתרון יהיה אקספוננציאלי(לא בP). הידע שלי במתמטיקה הוא סימלי לכל היותר, לכן לא היו לי יותר מדי בעיות לבחור מהן. עבור משוואות דיופונטיות ידעתי שיש משוואות שלא ידוע האם יש להן פתרון. אם היתה הוכחה שחיפוש הפתרון באמת מצריך מעבר כל כל המספרים בטווח, יכול להיות שההוכחה היתה עובדת. לרגע גם טעיתי לחשוב שאם החיפוש (של הפתרון) הוא ביעילות כל שהיא (שכמובן חייבת להיות תלויה בn, המספר המקסימלי בטווח שמחפשים בו), אני אוכל לבנות פונקציה שתרחיב את הטווח כך שזמן החיפוש עדיין יהיה אקספוננציאלי. אני באמת יכול לעשות את זה, אבל אז הפתרון גדל כל כך שאני כבר לא יכול לוודא את נכונותו בזמן פולינומי בA. | |
|
|
|
|
|
||
|
||||
|
הגישה שלך בכלל לא מופרכת. בפרט, היא פחות או יותר הבסיס לקריפטוגרפיה המודרנית; למשל, בעיית הפירוק לגורמים, שהיא 1 מה שעומד מאחורי RSA סובלת מקושי שכזה. הרעיון הוא שאפשר לייצג די בקלות מספרים גדולים, בני מאות ספרות (כי צריך רק מאות ביטים בשביל זה), וגם די קל לעבוד איתם - חיבור וכפל, למשל, הם פולינומיים במספר הביטים, וגם העלאה בחזקה מודולו משהו היא פולינומית במספר הביטים אם משתמשים באלגוריתם פשוט אך לא נאיבי; אבל פירוק לגורמים נאיבי דורש בדיקה של כל המספרים הקטנים ממה שרוצים לפרק 2 וכאלו יש במספר שהוא אקספוננציאלי במספר הספרות. כמובן, כבר ידועים אלגוריתמיים יותר מתוחכמים לפירוק לגורמים, אבל גם הם עדיין אקספוננציאליים, אם אין לך מחשב קוואנטי פועל בהישג יד. ------------ 1 לא בדיוק; אם פותרים פירוק לגורמים הלך על RSA, אבל אולי אפשר לחסל את RSA בלי לפתור את בעיית הפירוק לגורמים. 2 טוב, "עד השורש" הידוע. |
|
|
|
|
|
|
||
|
||||
|
בתחום הזה (תאוריה של מדעי המחשב) יש לישראל ייצוג מאוד מכובד1, במיוחד בהשוואה להישגים שלנו בענפים מתמטיים אחרים. לפעמים נדמה לי שאנחנו משקיעים יותר מדי מאמצים ואנשים טובים בכיוון. מאיפה אתם חושבים מגיעה המשיכה הזו של ישראלים לתחום הזה? ______ 1 רשימת הזוכים בפרס גדל (כ-30% ישראלים): רשימת המאמרים בשתי הועידות הגדולות של התחום (לכרבע עד שליש מהמאמרים יש מחבר ישראלי): |
|
|
|
|
|
|
||
|
||||
|
מי זה בדיוק "אנחנו"? מה זה בדיוק "יותר מדי"? | |
|
|
|
|
|
||
|
||||
|
אנחנו - ישראל, או האקדמיה הישראלית (כן, יש כזה דבר שנקרא אנחנו, אבל מכיוון שאתה מתעקש להוציא את עצמך מהכלל, אני אמנע מזה בהמשך). ''יותר מדי'' - חלוקת הכישרון המתמטי של ישראל נראית לא מאוזנת לכיוון של תאוריה של מדעי המחשב, והיכולות של ישראל בשאר התחומים המתמטיים סובלות מזה. |
|
|
|
|
|
|
||
|
||||
|
זה לא עניין של ''להוציא את עצמי מן הכלל''. זה עניין של הכרה בכך שאנשים בוחרים באקדמיה את מה שמעניין אותם, לא את מה שהאח הגדול אומר להם ללמוד. | |
|
|
|
|
|
||
|
||||
|
זה לא מדויק. לממשלה ולגורמים אינטרסנטיים יש מגוון דרכים להשפיע על הבחירה, ובמידה רבה הם אף עושים זאת. | |
|
|
|
|
|
||
|
||||
|
אז זה לא מעניין שבישראל יש נטייה חזקה דווקא לכיוון הזה? הרושם שלי הוא שיש נטייה בארץ ללכת לתואר ראשון שייתן מקצוע. זה גם הפולניות של ההורים ואולי גם קשור לעובדה שמתחילים את הלימודים אחרי הצבא. הרבה אנשים שהיו יכולים להיות מתמטיקאים או פיזיקאים לומדים מקצוע הנדסי בתואר הראשון. לעומת זאת, הביקוש לפיזיקה ומתמטיקה באוניברסיטאות הוא נמוך (אפשר לראות את זה גם בסף הקבלה לחוגים האלו לעומת מדמ"ח). לפני כמה שנים הייתה כתבה שבה התלוננו פרופסורים על הטרנד של לימודי מדעי המחשב (בגלל התדמית של הכסף הגדול והסטארט-אפ) שמשך אליו את האנשים הכי טובים וייבש את המקצועות שזקוקים להם יותר (הציטוט שאני זוכר הוא "לא צריך 750 בפסיכומטרי כדי להיות תכנת"). אני יודע, לדוגמא, שיש מחסור בסטודנטים לתארים גבוהים בפיזיקה, והעומס על המתרגלים בחוג הזה גבוה פי כמה מהעומס במדמ"ח. לדעתי, ההטייה הזו במחקר לטובת מדעי המחשב נובעת מההטייה שיש בתואר הראשון, כלומר היא נובעת מבחירה שאנשים עשו לגבי המקצוע העתידי שלהם (מקים סטרטאפ מיליונר/תכנת) שלא התממשה בכלל (מרצה). העניין הוא שכשאנשים הולכים ללמוד הם לא יודעים שהם ימשיכו לאקדמיה והם גם לא יודעים ממש מה לומדים באוניברסיטה. פתרונות אפשריים: הקמת מסלולים רב תחומיים, איתור מצטיינים בשלבים מוקדמים של התואר הראשון וטיפוחם לקראת קריירה אקדמית. |
|
|
|
|
|
|
||
|
||||
|
לבחור בתואר ראשון שייתן מקצוע זאת החלטה, אפעס, די הגיונית (במיוחד בהתחשב במצב המשרות באקדמיה, אבל בלי כל קשר). | |
|
|
|
|
|
||
|
||||
|
הגיונית בסביבה חסרת הגיון. | |
|
|
|
|
|
||
|
||||
|
הייתי אומר ''תואר ראשון שייתן גם מקצוע''. סטודנט הבוחר בתחום מדעי המחשב, מאפשר לעצמו התפתחות הן בצד המקצועי, והן בצד האקדמי - מה גם שהתחום האקדמי הוא די חדש בראי ההיסטוריה, ולהערכתי יש בו יותר מקום לפיתוחים וגילויים חדשים. |
|
|
|
|
|
|
||
|
||||
|
I'm an Israeli in this field that is currently living abroad. The quality of Israelis in this field is very high.
I can think of some possible reasons (I'll try to see below), but the question sounds really strange to me. If a scientific field is doing well, the question should be how do we copy this to other fields, and not how do we make it do less well... Generally, I think that the reasons that Israelis do relatively well in theoretical computer science are some mixture of: 1. As people said, many smart Israelis do their first degree in computer science and not say mathematics or physics. The reason is the job prospects. This is not unique to Israel - in the U.S. many smart people study law or business because it pays more than being a programmer or engineer. 2. When a good student then continues to do a Ph.D, they are naturally attracted to good professors. Therefore, if there are good Israeli professors in theory of CS then the good students will tend to study this as well. I think generally a small country can't be strong everywhere, so it's better to be strong in some areas, rather than being average everywhere. But in any case probably any attempt to "fix" this "problem"" will result in good people not going to Ph.D or quitting it or taking jobs abroad, rather than other areas becoming better. That's not to say that with some effort it's not possible to make Israel stronger in some other areas. But the way to do it is not to make us worse in theoretical computer science. In fact it's the opposite - excellence attracts excellence. |
|
|
|
|
|
|
||
|
||||
|
שימו לב למשהוא משעשע, הדרך הכי מהירה למיין היא הדרך הנאיבית! הסיבה לזה היא שאי אפשר לחפש ברשימה ממוינת במהירות של LOGn והסיבה לזה היא שאפילו אם אתה יודע במדויק את המיקום של איבר מסויים לוקח לך N צעדים להגיע אליו (הN פעולות הן "הזז את הראש הקורא צעד ימינה"). זהו... סתם רציתי שתדעו שכל מה שלמדתם על מחשבים לא תקף למכונות טיורינג :-) [כאתגר אתם מוזמנים לוודא שהאלגוריתם מיון מיזוג לוקח N בריבוע במכונת טיורינג...] |
|
|
|
|
|
|
||
|
||||
|
[צ] "זהו... סתם רציתי שתדעו שכל מה שלמדתם על מחשבים לא תקף למכונות טיורינג" [/צ] תקף תחת מגבלות ידועות. כל מודלי החישוב ההגיוניים המוכרים, או שחלשים ממכונת טיורינג, או ששקולים לה פולינומית. דרגת הפולינום זה סיפור אחר, וזה ידוע. |
|
|
|
|
|
|
||
|
||||
|
מה שדורפל אמר. נראה לי שאתה לא מבין מה מכונת טיורינג באה לעשות, ולמה (וגם לא איך עובדים מחשבים ''אמיתיים''). | |
|
|
|
|
|
||
|
||||
|
בדיון הסטנדרטי על סיבוכיות של מיון, המדד שמדברים עליו הוא מספר ההשוואות שהאלגוריתם מבצע ולא זמן הריצה שלו, בדיוק כדי לא להיות תלויים במודל. גם החסם של nlogn לסיבוכיות של מיון הוא חסם רק על מספר ההשוואות. בדרך כלל מדגישים את זה בקורס מבני נתונים. קח כתרגיל הביתה להוכיח שבמכונת טיורינג מרובת סרטים (נגיד 3) כשהאיברים למיון שייכים לאלף-בית של המכונה אכן אפשר למיין בזמן ריצה nlogn. |
|
|
|
|
|
|
||
|
||||
|
טוב בסדר אז השוואות :-) (ואני לא מצליח להבין איך אתה מקבל את הLOG N גם אם 3 סרטים (וזה לא בגלל שאתה טועה זה כי בגלל שאני לא חכם מספיק)) |
|
|
|
|
|
|
||
|
||||
|
אם שלושה סרטים לא תקבל לוג, עם אולי כן. | |
|
|
|
|
|
||
|
||||
|
אז ככה, כבר שנים שאני מסתובב עם בעיה שלמה ב NP שיש לי בשבילה פתרון לינארי- אפילו לא חזקה של n. שתי בעיות: 1) להראות שהבעיה שלמה ב NP. 2) להראות שהפתרון נכון תמיד. ניסיתי בעצמי רדוקציות ל SAT ולעוד בעיות שלמות אך ללא הועיל(קנס של 80 ש"ח לאוניברסיטה על איחור בהחזרת הספר ששכחתי את שמו ומתאר את הבעיות הנ"ל). כנראה שהבעיה אינה שלמה ב NP או שכוחי דל. את השלב השני נעבור אחרי הצלחות בשלב הראשון. מי שרוצה להתמודד עם הבעיה מוזמן לפנות אליי. אני בשמחה אשתחרר מהעול הזה, לכאן או לכאן. |
|
|
|
|
|
|
||
|
||||
|
כמו שאני מבין את זה, רדוקציה *ל*-SAT מבעיה שיש לה פתרון ליניארי לא תראה שום דבר. מה שאתה צריך להראות הוא שיש רדוקציה *מ*-SAT *ל*בעיה הנ"ל. אז או שאני מבולבל לרגע, או שאתה מבזבז את זמנך לגמרי כבר כמה שנים. | |
|
|
|
|
|
||
|
||||
|
כן, גם אני התעכבתי רגע כשכתבתי את התגובה ושיניתי מ'מ' ל'ל'. בו נתבונן בזה כך: נסמן את הבעיה שלי ב X ואת האלגוריתם שלי ב P. ובתור בעיית NP ניקח את SAT ואלגוריתם שפותר SAT ב S. עכשיו, ברור שקלט ל X ניתן להריץ על P וקלט ל SAT ניתן להריץ על S. אם נהפוך את הקלט של X ל קלט ל SAT הרי שהראנו ש X טובה לפחות כמו SAT. לא מועיל בהרבה. אבל, אם נראה שאת הקלט של SAT ניתן להפוך לקלט ל X אזי נריץ את P עם הקלט המקורי של SAT, נקבל תשובה בזמן לינארי ולמעשה הפכנו את SAT ללינארית. לסיכום: יש לעשות רדוקציה מ SAT ל X על-מנת להראות ש P=NP, בלי סימן שאלה. אנא תקנו אותי אם הצלחתי לבלבל את עצמי שוב. בכל מקרה. הבעיה עדיין פתוחה: האם הבעיה שיש בידי, כולל הפתרון הלינארי טובים? האם X שלי ב NP או לא? והאם P שלי אכן פותר את כל המקרים. SIMPLEX הוא אלגוריתם שנראה טוב אבל יש קלטים שבהם הוא "נופל". האם גם P כזו? זאת ועוד בפתיל התגובות להלן... |
|
|
|
|
|
|
||
|
||||
|
מצטער, אני מאוד לא אוהב לקרוא טקסטים שהם פחות מברורים לגמרי. אם אתה מעוניין בדעתי, אעדיף למסור לך אותה בצורת הסבר מחדש של הנושא, בלי לנסות לפענח - איתך הסליחה - את מה שכתבת. ידוע שכל בעיה ב-NP, ניתן, בזמן פולינומי, להמיר בבעיית SAT. כלומר, אם אתה רוצה לדעת, למשל, אם יש מעגל המילטוני בגרף שעובר דרך כל הקודקודים, אתה יכול, בזמן פולינומי, ליצור פסוק בוליאני שניתן לסיפוק אם ורק אם היה בגרף שהתחלת ממנו את התהליך מעגל כנ"ל. בשלב הזה, אם מישהו יודע לפתור את SAT בזמן פולינומי, אתם יכולים לעבוד ביחד בכדי לפתור בזמן פולינומי את הבעיה המקורית שלך: אתה תיקח את הבעיה שלך, תמיר אותה בבעית SAT, תמסור אותה לבחור שיודע לפתור בעיות SAT, הוא יחזיר לך תשובה, ואתה תחזיר את התשובה שקיבלת ממנו. כל אחד משני השלבים נעשה בזמן פולינומי, ויחד זה עדיין פולינומי. כלומר, יוצא שאם את בעית SAT ניתן לפתור בזמן פולינומי, אז כל בעיה ב-NP ניתנת לפתירה בזמן פולינומי, ע"פ התהליך הנ"ל (אותו לא תיארתי במלואו. אמרתי שידוע שאפשר לבצע המרה כזאת לכל בעיה ב-NP, אבל לא אמרתי איך). חשוב לשים כאן לב שהבעיה שלך עשויה להיות הרבה יותר פשוטה מהבעיה שאתה מוסר לו הלאה. לדוגמה, אתה יכול להתמודד עם הבעיה המאוד פשוטה של "האם המספר שאני עומד מולו כרגע הוא המספר 31, או כל מספר אחר?" במקרה המנוון הזה, אתה יכול לפתור בקלות את הבעיה, ואז להעביר הלאה, לבחור שפותר את SAT, במידה וקיבלת את המספר 31, את הפסוק "א' או ב"', ובמידה וקיבלת מספר אחר, את הפסוק "א' או לא א"'. התשובה שלו לראשון תהיה "כן", ולשני "לא", אבל אתה לא תלמד מכך שום דבר חדש. מה שאתה מחפש להוכיח הוא ש-SAT ניתנת לפתירה בזמן פולינומי. קלאסית, אתה תנסה לעשות את זה על ידי הצגת אלגוריתם שפותר את SAT בזמן פולינומי. דרך אחת לעשות את זה היא להראות שיש בעיה אחרת, שניתן לפתור אותה בזמן פולינומי, ושניתן להמיר *את SAT בבעיה החדשה הזאת בזמן פולינומי*. שים לא - לא את הבעיה החדשה בבעיית SAT, אלא את בעיית SAT בבעיה החדשה. |
|
|
|
|
|
|
||
|
||||
|
אם אתה רוצה לדבר בחידות, בבקשה, אבל אין סיבה שמישהו יתייחס אלייך ברצינות. תספר מה הבעיה ומה הפתרון, וחסל. אגב, חשוב לזכור שהרדוקציה מ-SAT לבעיה שלך צריכה להיות ניתנת לחישוב בזמן פולינומי. רדוקציה לא פולינומית מ-SAT יש לכל דבר שבעולם (כמעט). |
|
|
|
|
|
|
||
|
||||
|
אפשר דוגמא (לרדוקציה לא פולינומית מSAT או מבעיה NP-שלמה אחרת לבעיה פולינומית)? | |
|
|
|
|
|
||
|
||||
|
בטח. למשל, הבעיה של "האם x הוא 1?" כש-x הוא בתחום 0 או 1. הרדוקציה היא כזו: בהינתן פסוק בתחשיב הפסוקים, בדוק (בזמן אקספוננציאלי, בצורה הנאיבית) אם הוא ספיק. אם כן, העתק אותו ל-1. אם לא, העתק אותו ל-0. מה קיבלנו? שפסוק הוא ספיק אם ורק אם הוא מועתק ל-x שעליו האלגוריתם שפותר את הבעיה הפשוטה עונה "כן". |
|
|
|
|
|
|
||
|
||||
|
ועוד דבר, את החלק של רדוקציה מ SAT לבעית סידור ההזמנות לא הצלחתי להראות בכלל. כלומר אין לי שום אלגוריתם שהופך את SAT לבעית סידור ההזמנות. כך שבוודאי שהוא לא פולינומי. יש לכם משהו? |
|
|
|
|
|
|
||
|
||||
|
זו הפעם הראשונה שבה אני שומע אותך אומר משהו על "סידור הזמנות", אז עדיין לא ברור על מה אתה מדבר. בכל אופן, הצעד הראשון לפני שמתקלים את P=NP הוא לבדוק שניתן לבצע רדוקציה פולינומית מ-SAT (או בעיה NP-שלמה אחרת) אל הבעיה שיש לך ביד . אם אין לך משהו כזה, אין לך בעצם כלום (כלומר, יש לך בעיה שאתה יודע או לא יודע לפתור, אבל אין לה קשר ממשי לשאלת P=NP). |
|
|
|
|
|
|
||
|
||||
|
אני כתבתי תאור ארוך של בעיית סידור ההזמנות, חשבתי שתראה את התגובה ההיא לפני זאת ולכן כבר התיחסתי אליה כאל בעיה שאתה מכיר... תיכף אני אתאר אותה שוב. משום מה היא לא עלתה למערכת (תגיד, צריך ללחוץ על "אישור"? :-)) מלבד זאת, אני לא תוקף את P=NP אני רק רוצה לשייך את בעיית סידור ההזמנות למחלקה הנכונה. בשלב ראשון זה מה שאני לא יודע. אח"כ כבר יהיה יותר קל: אם היא שייכת ל P אזי נוכל להניח שהאלגורתם שמסדר הוא נכון תמיד. אם הבעיה שייכת ל NP אזי נצטרך לעבוד קצת יותר קשה ולהראות שיש לפחות קלט אחד שעבורו האלגוריתם רץ בזמן לא סביר. להלן (שוב) תיאור הבעיה: נתון צי רכבים N. לכל רכב בצי יש מספר תכונות המאפיינות אותו: מספר מקומות, סוג הילוכים, רשיון נדרש, צבע וכד'. נתונה רשימת הזמנות R. כל הזמנה מכילה: 1. מאיזו שעה ועד איזו שעה הרכב נדרש. 2. מאפיינים של הרכב הנדרש. הרשימה יכולה להיות ריקה, כלומר כל רכב מתאים. השאלה: האם קיים סידור ל R ב N? או בגרסה המלאה: מהו הסידור של R ב N? כל מי שהיה פעם חבר קיבוץ מכיר את הבעיה. יש לי גם תאור פורמלי יותר של הבעיה, יותר מאוחר אני אעלה אותו. |
|
|
|
|
|
|
||
|
||||
|
בלי לחשוב על הבעיה יותר מדי, היא נראית לי הרחבה של http://en.wikipedia.org/wiki/Knapsack_problem שהיא בעיה NP שלמה. | |
|
|
|
|
|
||
|
||||
|
במבט חטוף, אני לא מצליח להבין אם יש קשר בין שתי הבעיות. אולי, אם כל פריט הוא הזמנה: משקלו הוא השעות וערכו הוא התיקים אליהם הוא יכול להכנס?... לא נשמע טוב, צריך לבדוק. ודווקא הרחבה יכולה ליצור הקלה בתנאים ולהפוך את הבעיה לפשוטה יותר.... | |
|
|
|
|
|
||
|
||||
|
הנה תיאור של רדוקציה מבעיה דמוית-תרמיל לבעית סידור ההזמנות. הבעיה (דמוית התרמיל): נתונות n משקולות, במשקל כולל N, וצריך למצוא תת קבוצה שלהן כך שסכום המשקולות בתת הקבוצה הוא *בדיוק* K. בנוסף אני דורש ש- 2K>N. רדוקציה: בצי הרכבים יש שני רכבים, 1 ו- 2. אורך ה"יממה" הוא K שעות. כל משקולת הופכת להזמנה של רכב למספר שעות השווה לגודל המשקולת, כאשר ההזמנה היא לרכב 1 או לרכב 2. בנוסף, יש הזמנה של 2K-N שעות לרכב 2 בלבד. סכום השעות בכל ההזמנות הוא בדיוק 2K, וכך גם סכום השעות הזמינות. לכן אם יש פתרון, הוא יהיה חייב לקיים שסכום ההזמנות של רכב 1 הוא בדיוק K, כנדרש. עכשיו, כדי לצמצם את "הפער" בין הבעיה דמוית התרמיל שהצגתי לבין בעית התרמיל המקורית ניתן לפעול בשתי דרכים: או למצוא רדוקציה מבעית התרמיל לבעיה דמוית התרמיל, או לפתח את הרדוקציה הזאת כך שתפתור בעיה יותר כללית. הנה כמה מחשבות על הדרך השניה: הדרישה ש- 2K>N היא דרישה טכנית, שלדעתי אפשר להיפטר ממנה. מה שבטוח הוא שבאופן טריביאלי אפשר לשים כל קבוע אחר במקום ה- 2. לגבי העובדה שאנחנו מוצאים פתרון רק אם הסכום הוא בדיוק K - את זה אפשר היה לפתור אילו בבעית ההזמנות היתה איזושהי "עדיפות" (כלומר, כל כותב הזמנה היה כותב באיזה עדיפות הוא רוצה אילו רכבים, והיינו יכולים להכניס garbage collector נוסף - רכב 3 - שהיה אוסף את כל מי שלא קיבל את הזמנתו). זה גם היה מאפשר להכניס פנימה את עניין הערך לעומת גודל המשקולת לדעתי (אם כי לפי זכרוני המעומעם כבר יש רדוקציה לבעיה שבה הערך הוא המשקולת). זאת בקצרה ובלי לחשוב יותר מדי, והתחושה שלי (בדומה ל- easy) היא שעם נעבוד קצת יותר נגיע לרדוקציה. |
|
|
|
|
|
|
||
|
||||
|
שים לב שכחלק מההזמנה צריך לציין מאיזו שעה עד איזו שעה הרכב נדרש. התכונה הזו מקלה מכיוון שהיא מורידה באופן משמעותי את דרגות החופש של הפתרון. | |
|
|
|
|
|
||
|
||||
|
מצד אחד היא מקלה כי היא מצמצמת את החופש אך מצד שני היא מקשה על האלגוריתם למצוא סידור. חופש בהזזת עשות ההזמנה היה מקל על האלגוריתם, ויתכן אפילו שאחד חמדן היה מוצא פתרון טוב. אגב, האלגוריתם הנאיבי שפותר את הבעיה הוא: 1. כל עוד אין התנגשות שבץ את ההזמנה הנוכחית במקום שמתאים לה. 2. אם אין מקום להזמנה הנוכחית, חזור להזמנה הקודמת ומקם אותה במקום אחר שמתאים לה ושהיא עוד לא היתה בו אף פעם. 3. חזור ל 1. נאיבי, אקספוננציאלי אבל עובד. |
|
|
|
|
|
|
||
|
||||
|
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת. | |
|
|
|
|
|
||
|
||||
|
הערה טכנית: אלגוריתם דטרמיניסטי לא "עובד תמיד נכון", הוא או עובד נכון (תמיד), או לא נכון (מספיק שבמקרה אחד). עוד הערה טכנית: את הבעיה לא הסברת "שוב", הסברת אותה לראשונה. אם אתה מתכתב בנושא בכמה פורומים, מן הנימוס שתזכור עם מי דיברת על מה, או לפחות לא תנזוף באף אחד על שכחה. |
|
|
|
|
|
|
||
|
||||
|
הוא הסביר אותה "שוב", בפעם הראשונה "משום מה היא לא עלתה למערכת" תגובה 468939 (אם אתה נוזף באחרים כדאי שתבדוק שאתה לא נוזף בהם בטעות). | |
|
|
|
|
|
||
|
||||
|
לא הבנתי שכשהוא אומר שהוא ''תיכף יתאר אותה שוב'', הוא מתכוון באותה הודעה ממש. חשבתי שהוא מתכוון עוד שעתיים, כשיגיע זמן הפסקת הצהריים. תודה על התיקון, וסליחה לרן. | |
|
|
|
|
|
||
|
||||
|
עוד לא העליתי את התאור הפורמלי של בעיית סידור ההזמנות, פשוט זה בבית ועוד לא היה לי את הפנאי. אם זה ידרבן מישהו מהקוראים להתעסק עם זה, אני אעלה גם את האלגוריתם. שאלה: מה המשתנה, n, שעליו ניתן לומר שהאלגוריתם עובד ב O כלשהו של n? האם זה צי הרכבים N, האם מספר ההזמנות R? ועוד שאלה: האם טווח השעות בבעיה משנה לשייכותה למחלקה זו או אחרת? כלומר, אם הזמן בו ניתן לבקש רכב הוא סופי, למשל 24 שעות. או אם הזמן הוא לאינסוף. |
|
|
|
|
|
|
||
|
||||
|
לרוב נהוג כשעוסקים בהיבטים תיאורטיים כמו P מול NP לדבר על גודל הייצוג של הקלט. לכן לא סופרים כמה רכבים והזמנות יש, אלא האם כמה מקום לוקח לייצג אותם (בדומה לצורה שבה פונקציות על מספרים נמדדות בסיבוכיות שלהם לא ביחס לגודל המספרים, אלא לגודל הייצוג שלהם, שהוא לוגריתמי בגודל המספר כשאנחנו בבסיס ספירה גדול מ-1). | |
|
|
|
|
|
||
|
||||
|
למעשה אתה טוען שזה שקלול של השניים. זה בסדר, אין לי בעיה עם זה. ומה לגבי מהותו של עניין - לאיזו מחלקה הבעיה שייכת? |
|
|
|
|
|
|
||
|
||||
|
הבעיה שאתה מציג היא מסוג בעיית תזמון משאבים בגרף אינטרוולים. הבעיות האלה מעניינות בהקשר של P/NP כיוון ששינוי מאוד קטן בהגדרת הבעיה מעביר אותה מ- P ל- NPC. ספציפית נראה לי שהבעיה שאתה מתאר נמצאת ב- P אבל אני לא יודע להציג לה אלגוריתם ובפרט אני לא רואה אלגוריתם "סטנדרטי" שעובד בזמן ליניארי (אני חושב שצריך זמן ריבועי או משהו כזה). | |
|
|
|
|
|
||
|
||||
|
כמו שאמרו כאן, זו בעייה בסגנון "Interval Graph". אני לא מבין כלום בנושא, אבל אני מכיר מישהו שמבין ואשאל אותו. | |
|
|
|
|
|
||
|
||||
|
זה מאד יעזור, תודה. | |
|
|
|
|
|
||
|
||||
|
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות. (אם הקשר לא ברור - "צבע" מתאים לרכב כלשהו; הצמתים בגרף מסמנים משימות; יש קשת בין שני צמתים אם ורק אם אלו משימות ש"עולות" אחת על השנייה; הצבעים החוקיים לצביעת צומת ספציפית הם צבעי כל הרכבים שהפרמטרים שלהם מתאימים למשימה שהצומת מייצגת). |
|
|
|
|
|
|
||
|
||||
|
טוב, גם לי אין תשובה חד משמעית... :-) כנראה שזה ישאר פתוח. היתה לי איזו תקווה שמישהו מהקוראים ירים את הכפפה, יקח את הבעיה ואת הפתרון ויוכיח משהו. לא נורא. אני אעשה עוד נסיון אחד, להעלות את הניסוח הפורמלי, הן של הבעיה והן של האלגוריתם, אולי זה יעיר מישהו. :-| רן. |
|
|
|
|
|
|
||
|
||||
|
אולי הוא מתכוון ל-PCP? אמנם זו בעיה בלתי-כריעה, לא ב-NP, אבל... מכך שזה לא נכון, לא הייתי קופץ למסקנה שלא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
לא, לפי המשך השרשור, לא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שהבעיה נקראת staff scheduling ונהוג לפתור אותה עם integer programming. | |
|
|
|
|
|
||
|
||||
|
http://en.wikipedia.org/wiki/Linear_programming#Inte... היא בכלל בעיה NP קשה (כך שלא ממש נהוג לפתור אותה). | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת "לא ממש נהוג לפתור אותה"? | |
|
|
|
|
|
||
|
||||
|
לבעיות שמצריכות תכנון בשלמים, במקרה הכללי, אין פתרון ישים. | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת אין פיתרון ישים? ברור שיש פיתרונות, רק שלא תמיד הם אופטימליים. | |
|
|
|
|
|
||
|
||||
|
נדמה לי, ותקן אותי אם אני טועה, שהבעיה שהוצגה כאן היא בעיית אופטימיזציה. | |
|
|
|
|
|
||
|
||||
|
אכן. לבעיות אופטימיזציה שהן NP-קשות נהוג למצוא פתרונות מקורבים. יש תחום מחקרי שלם (ומרתק) על "עד כמה טוב אפשר לקרב בעיה מסויימת בלי לקבל ש-P=NP". מסתבר שבעיות NP-שלמות נבדלות זו מזו באופן דרסטי במידת הקירוב האפשרית שלהן. | |
|
|
|
|
|
||
|
||||
|
הקדים ואומר תודה לכותב המאמר. רציתי לשתף בדוגמא מעניינת לתוכנית שכתבתי לפני כשלוש שנים בשפת c שגיליתי שעל קלטים קטנים היא רצה במהירות רבה(פחות משניה) ועל קלטים טיפה יותר גדולים היא צריכה יותר מגילו של העולם בשביל לפתור. התוכנית הייתה אמורה למצוא פיתרון יחיד(או את כל הפתרונות) של חידת המלכות. חידת המלכות : הגדרה של מלכה בשחמט - כלי שיכול לנוע באלכסון שמאלה ימינה למעלה ולמטה לכל אורך הלוח. המטרה היא לשים 8 מלכות על לוח שח מט(בגודל 8 על 8 משבצות כמובן) כך שאף מלכה לא תוכל במהלך אחד להגיע למלכה אחרת. נסו לבדכם את החידה, תראו שהיא לא כל כך קלה אך אחרי כמה נסיונות סיכוי גבוה שתמצאו פיתרון אחד מבין ה-80 ומשהו פתרונות אפשריים. בשביל לתאר כמה זמן לוקח לתוכנית אתאר איך פועלת התוכנית בכלליות: מכיוון שכל מלכה יכולה לזוז למעלה למטה אפשר להניח מראש כבר שכל תור יהיה בו מלכה אחת יחידה. התוכנית מתחילה מהמצב שכל שמונה המלכות נמצאות בשורה הראשונה כל אחת בתור שלה. כל פעם התוכנית מזיזה את המלכה הימנית ביותר שורה אחת קדימה. ברגע שהמלכה הימנית ביותר הגיעה לשורה האחרונה בתור הבא המלכה הימנית ביותר חוזרת לשורה הראשונה והמלכה משמאלה עוברת שורה קדימה. אם המלכה משמאל לימנית ביותר מגיעה לשורה האחרונה היא חוזרת לשורה הראשונה והמלכה משמאלה עוברת שורה אחת קדימה. וכך הלאה עד שכל המלכות נמצאות בשורה האחרונה. זה לא האלגוריתם האידאלי אך הוא התאים לי כשרציתי לפתור את הבעיה. בשביל להבין את הסיבוכיות של האלגוריתם יש לציין שכל מלכה יכולה להיות בכל שורה בתור שלה. ולכן לכל מלכה יש 8 אפשרויות איפה להיות. ויש 8 מלכות. ולכן יש 8 בחזקת 8 מצבים אפשריים שהאלגוריתם בודק. זהו מספר לא קטן בכלל. למעשה זהו מספר עם 7 ספרות. ניתן למצוא אלגוריתם יותר יעיל וכמובן שיש את האלגוריתם הכי פחות יעיל שכל מלכה יכולה להיות בכל מקום פנוי כלומר כמות האפשרויות היא 64*63*...* 57 שזהו מספר עם 14 ספרות. עכשיו התוכנה פתרה את הבעיה תוך זמן שלא ניתן להבחין בו(פחות מחצי שניה). ולכן ניסיתי לשנות את גודל הלוח ואת מספר המלכות(מספר המלכות הוא כמובן ביחס ישר לגודל הלוח). ופה מסתבר שעבור לוח בגודל 1-8(כלומר 1 על 1 עד 8 על 8 משצבות) זמן הריצה הוא אפסי. עבור לוח של 9 על 9 משבצות זמן הריצה הוא כמה שניות. עבור 10 אחרי הרבה דקות. בואו נניח שבדיקת מצב לוקחת פעולת מעבד בודדת. כלומר ב-8 על 8 יש 10 בחזקת 7 פעולות. המחשב עובד על 3 גיג'ה הרץ. כלומר 3*10 בחזקת 9 פעולות בשניה. כלומר זמן הריצה קטן מ-שניה. עכשיו עבור לוח של 12 על 12 יש 12 בחזקת 12 מצבים כלומר 9 כפול 10 בחזקת 12. נחלק את המספר במהירות שעון(3 גיג'ה) זה 3000 שניות. כלומר כמעט שעה. עבור לוח של 15 על 15 : 10 בחזקת 17 מצבים. לוקח לפי מהירות השעון הזאת 4.5 שנים. עבור 17 על 17: 10 בחזקת 20 פעולות. 8700 שנה. עבור 20 על 20 : 10 בחזקת 26. 1.1 מליארד שנה. עבור 25 על 25 : 10 בחזקת 34 מצבים. 938798431.1 מליארדי שנה. יש לזכור שהעולם קיים רק כמה מליארדי שנים בודדות. עכשיו נניח שמשפרים את יעילות האלגוריתם פי 10(וזה הרבה... אולי אפשרי אבל לא פשוט), ונניח שיש מחשב שבמקום לחשב 3*10 בחזקת 9 פעולות בשניה מחשב 10 בחזקת 20 פעולות בשניה(מדובר על עצום. פי מאה מליארד יותר מהר) עדיין עבור לוח של 25 על 25 הזמן שיקח לפתור את הבעיה הוא מליון שנים. ככה שכנראה לעולם לא נוכל לפתור את הבעיה של חידת המלכות עבור לוח של 25 על 25 ע"י האלגוריתם שתואר. בלי קשר להתפתחות הטכנולוגיה. ועם בטעות נוכל לפתור עבור לוח של 25 על 25 משבצות לא נוכל לעשות זאת על לוח של 35 על 35 משבצות. *נ.ב כמובן שבדיקת מצב אינה פעולה יחידת של המעבד, לצורך הדיון אפשר להתייחס לכל תהליך בדיקת המצב כפעולה יחידה. בפועל לא התפלא כלל אם בדיקת מצב יחיד לוקחת עשרות אלפי פעולות מעבד. |
|
|
|
|
|
|
||
|
||||
|
פתרון לגדלים שלא מתחלקים ב 2 או 3: --#-------- ----#------ ------#---- --------#-- ----------# -#--------- ---#------- -----#----- -------#--- ---------#- #---------- חסכנו מיליארד שנה עכשיו נותרו עוד שני שליש מהמקרים |
|
|
|
|
|
|
||
|
||||
|
האם יש הוכחה שלכל לוח (ריבועי) יש לפחות פיתרון אחד לבעיה? | |
|
|
|
|
|
||
|
||||
|
ללוח 2X2 אין פתרון | |
|
|
|
|
|
||
|
||||
|
צודק. וחוץ ממנו? | |
|
|
|
|
|
||
|
||||
|
בסדר, בסדר, התכוונתי האם יש מספר שהחל ממנו תמיד יש לפחות פיתרון אחד, והאם המספר הזה הוא ליד 8. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שזה מספק אינטואיציה, גם אם לא הוכחה ממשית: (מספר פתרונות לבעיה כפונ' של מספר המלכות) |
|
|
|
|
|
|
||
|
||||
|
תודה! יש הכללה למימדים גבוהים? | |
|
|
|
|
|
||
|
||||
|
אני לא יודע על הוכחה, אבל החל מ 4X4 (ארבע זה ליד 8?1) יש פתרון, שכמובן אינו יחיד, כי אתה תמיד יכול לסובב את הלוח ב 90° (ארבעה פתרונות "שונים") וגם להציב אותו מול מראה. ___ 1 כשהייתי שסין לאחרונה, שאלתי את אחד הסינים שעבדתי מולו, האם הוא במקורו משנחאי. הוא השיב שהוא מעיר ליד שנחאי. מה זה ליד? במכונית ארבע שעות נסיעה. |
|
|
|
|
|
|
||
|
||||
|
כאשר הרצתי את התוכנה למצוא את כל הפתרונות אז מ-5 ועד 10 או 12 כמות הפתרונות רק הלכה וגדלה. זה לא מוכיח כלום אבל זאת אינדקציה. כאשר הרצתי את התוכנה למציאת פיתרון יחיד נמצא פתרון לכל המספרים הגדולים מ-5 עד 20(מעבר לזה היו בעיות בתוכנה שנבעו בעיקר משום שהשתמשתי ב-dos לא משהו שאי אפשר לפתור). לפי דעתי יש הוכחה שיש פיתרון יחיד עבור כל n>5 (כאשר n מספר השורות והעמודות). וגם יש טכניקה למצוא פיתרון יחיד שכזה. אבל לא בטוח בקשר לעניין. |
|
|
|
|
|
|
||
|
||||
|
מתמטיקסם | |
|
|
|
|
|
||
|
||||
|
מזמן לא קראתי מאמר כל כך מסובך שאת התגובות שלו אפילו לא הצלחתי להעמיד פנים שאני מבין. ואחר כך אומרים שרופאים מדברים בשפה סודית....<אנחה>. |
|
|
|
|
|
|
||
|
||||
|
אחחחחח דוקטור! אתה כל כך עוזר לי עכשיו! אמא שלי צדקה ששרינק זה בכלל לא מקצוע ורופא פנימי זה יותר טוב מאלף שרינקים!!! אחחחחח דוקטוווור!!! עוווווווווד!!!!!!!!!! |
|
|
|
|
|
|
||
|
||||
|
אם משהו לא ברור, אני יכול לנסות להסביר (אמנם, כנראה שהנסיון הראשון לא היה מוצלח, אבל אין חכם כבעל נסיון). | |
|
|
|
|
|
||
|
||||
|
' גמני, בגלל גולמיותי הבסיסית כנראה, ובעיקר עקב המוסיות הקנדית, משתאה נוכח צביר ההודעות הזה מיום היווסדו ועד לשלהי התגובות בהווה. ראבאק, על מה מדובר פה?! _____________ הכותב חש רגשי נחיתות עזים במסורת SAT ו-PN=NP או בערך |
|
|
|
|
|
|
||
|
||||
|
שוב - מה לא ברור? את הכל אפשר לנסות להסביר. | |
|
|
|
|
|
||
|
||||
|
' סליחה, לא רוצה להעיק מהבסיס. רק כבר כמה ימים שאני משפשף את המצח בתזזית. בודק כל כמה שעות אם לא חלה אצלי צניחה חופשית ברמת חיבורי הנוירונים במוח, ובעיקר - מפנים את ההכרה כי קיים עולם מושגים שלם שאין לי שום גישה אליו. זה לא אתה. זה בהחלט אני. עזוב, אין צ'אנס שאבין. תתעסק עם החבר'ה הטובים מהתגובות מרובות האיברים עם משוואות N פולינומים ויתר האלוגריתמים המיותמים. אבל תודה על האמפטיה והנכונות להדרכה במשעולי הלא-נודע במתמטיקה. ________________ הכותב הולך לפתור משוואה עם נעלם אחד ובודד במטרה להציל את כבודו העצמי בעיני עצמו |
|
|
|
|
|
|
||
|
||||
|
אני ממש לא מסכים, אבל מילא. | |
|
|
|
|
|
||
|
||||
|
סתם, אני סקרן לדעת איזה צורך אתה מספק בכתיבת הודעות שמנסות לשכנע את כותב המאמר ושאר הקוראים בכך שאינך מסוגל להבין משהו? לא עדיף לכתוב: "לא הבנתי למה מ-X נובע Y", או משהו בסגנון? גם חוסך זמן (וביטים) וגם עשוי לעזור לכותב להבין מהן בדיוק הנקודות שבהן קוראים חסרי השכלה בתחום עלולים להתקשות. אחרי שאתה צובר ידע ואינטואיציה בתחום מסויים, לפעמים קשה לחזור (אפילו בסימולציה) למצב "הבסיסי" ולהסביר מושגים שנראים לך טריוויאליים. ולמרות הטון המעט זועף, אני מקווה שתקבל זאת ברוח טובה. |
|
|
|
|
|
|
||
|
||||
|
' בטח שמקבל את הדברים כפשוטם וללא טענות ומענות. במיוחד שגם אתה ובמיוחד כותב המאמר בכבודו ובעצמו טורחים להבין מה מקור הבאג אצלי ולנסות ולהפיץ את המידע הנמצא ברשותכם גם לקוראים פחות מיומנים. לא הייתי מעלה בדעתי לומר זאת לולא ראיתי הודעה קודמת ששיקפה בדיוק את תחושתי. ככותרת פתיל המשנה הנוכחי. מכיוון שהתאמצתי לשווא לקרוא ולקלוט את הנכתב בגוף המאמר ובתגובות - מצאתי לנכון להביע את תסכולי מעצמי בצמוד לדברי הד''ר. זה הכל. כנראה שהחומר המובא כאן ספציפי ומקצועי מדי להדיוטות שלא עוסקים בתחום. עובדה היא שרבים המה המגיבים והמתדיינים שכן מוצאים שפה משותפת ואף מוסיפים כהנה וכהנה לשיח המתמטי. אני יכול רק לקנא בכם. |
|
|
|
|
|
|
||
|
||||
|
אני יכול לומר בודאות שהחומר לא *אמור* להיות "ספציפי ומקצועי". במקום שבו אני כשלתי, אולי דוד הראל יצליח - אני ממליץ על "המחשב אינו כל יכול" שלו. |
|
|
|
|
|
|
||
|
||||
|
' אתה טועה! החומרים מהם נחצבו שני המאמרים הינם סופר ספציפיים-מקצועיים מתחום המתמטיקה ומדעי המחשב. זר לא יבין זאת (כמעט). אבל צדקת, ותודה לך (וכמובן גם ל-MRP). בגלל התעקשותך להוסיף לי תובנות, חזרתי לקרוא - הפעם כקורס לימודי, ובניחותא. כיצור התופש עצמו כרציונלי הרצתי אלגוריתם פשוט על קלט של פונקציית הזמן שהקדשתי עד עתה לעניין, בשילוב עם מכונת טיורינג אוניברסלית למחצה בעלת תמסורת P, במטרה להבין על מה לעזאזל קורה כאן. להגיד לך שהצלחתי עד תום? לא ממש. אממה, קיבלתי מושג-מה. בערך כמו השערת גולדבך. תמיד יישאר ספק בגין אלמנט העצירה. בכל מקרה, שוב, תודות לך ולMRP, שגרמתם לי להתנער מעצלנות/שטחיות מחשבתית, ולהתאמץ לרכוש עוד ידע באמצעות האתר הזה. _____________ הכותב כבר מתכנן לעשות רושם על אישה מסוימת דרך דיון בלולאות אינסופיות והשיטה לעצירתן |
|
|
|
|
|
|
||
|
||||
|
אתה מתבקש לדווח על רמת הצלחתך /הרשמתך. | |
|
|
|
|
|
||
|
||||
|
' דיווח: עשיתי רושם עילאי. היא תלתה בי עיניים מוקסמות ועגולות לגמרי מפליאה (שלא לומר תדהמת מוחלטת על מה לעזאזל קורה פה), והפנתה אותי לעבר עיסוקים יותר ארציים. למשל, מה תעדיף שאקנה לה כמתנת יום הולדת. והכי חשוב כמה (קראט). כמובן בהקשר של מספרים ראשוניים. |
|
|
|
|
|
|
||
|
||||
|
מה שלא הבנתי לגבי הRSA הוא שמוצאים שני מספרים ראשוניים שהמכפלה שלהם נותנת מספר שלישי, נכון? המספר השלישי הזה חייב להיות מספר גדול מאוד, על מנת שלא ניתן יהיה למצוא את הפירוק שלו לגורמים בזמן סביר, עד כאן, נכון? מה שלא ברור לי הוא איך מלכתחילה מוצאים את שני המספרים הראשוניים האלו (שאמורים להיות מספרים גדולים מאוד)? |
|
|
|
|
|
|
||
|
||||
|
הם מאוד גדולים, אבל הם לא גדולים כמו המכפלה של שניהם... | |
|
|
|
|
|
||
|
||||
|
כדי למצוא "סתם" מספר גדול אין לנו שום בעיה - פשוט מגרילים ספרות (כדי להגריל מספר בן 500 ספרות, צריך לבצע 500 הגרלות של מספרים בין 0 ל-9 - לא קשה במיוחד). הבעיה היא, אם כן, לבדוק עבור מספר גדול אם הוא ראשוני או לא. זו אכן בעיה מעניינת, מבחינה חישובית. למעשה, עד תחילת האלף הנוכחי לא היה ידוע אף אלגוריתם דטרמיניסטי שעושה את זה בזמן סביר, והגילוי של אלגוריתם כזה (AKS) היה סנסציה זוטא. אלא מה? כבר הרבה לפני AKS היו כמה וכמה אלגוריתמים הסתברותיים מהירים מאוד לבדיקת ראשוניות. ב"הסתברותיים" הכוונה שיש להם סיכוי לטעות, אבל אם משלמים מחיר נמוך למדי בזמן הריצה, הסיכוי הזה הופך לאפסי. אלגוריתם מאוד מוכר ומקובל הוא אלגוריתם מילר-רבין [ויקיפדיה], שעשוי בטעות להגיד על מספר לא ראשוני שהוא כן ראשוני, אבל הסיכוי נמוך יחסית אם עושים מספיק בדיקות. הרעיון הבסיסי של מילר-רבין הוא שימוש במבחן שמספק "המשפט הקטן של פרמה [ויקיפדיה]", תוך כדי הוספת התחכמות קטנה שמטפלת במקרי קצה מעצבנים. אם תרצה, אפרט עוד על העניינים הטכניים. |
|
|
|
|
|
|
||
|
||||
|
עד תחילת האלף הנוכחי? כלומר, אחרי שנת 2000? ממש ממש בשנים האחרונות? וואלה? כלומר, כאשר RSA הוציאו את הפטנט שלהם הוא היה ישים רק בשילוב עם אלגוריתם *סטטיסטי* לבדיקת ראשוניות? האם תוכל לתת סדר גודל של עד כמה הסיכוי לשגיאה הוא נמוך? כלומר, עד אז, ואולי אפילו עד היום (עקב אי עדכוני תוכנה), קורה לעיתים רחוקות שהRSA נכשל, כלומר שהודעות מוצפנות, למשל בתקשורת שלי מול הבנק באינטרנט, לא ניתנות לפיענוח (ואז אולי יש מן תהליך כזה שמבקש את ההודעה שוב עם מפתח חדש)? |
|
|
|
|
|
|
||
|
||||
|
AKS פורסם לראשונה רק בשנת 2002. חשוב להדגיש שעד כמה שאני יודע, אף אחד לא משתמש בו בפועל; הוא מהווה תוצאה תיאורטית חשובה מאוד, אבל הוא איטי מדי לצרכים מעשיים, בהתחשב באלטרנטיבות. הסיכוי לשגיאה של מילר-רבין (ושל כל אלגוריתם הסתברותי בעל ערך אחר) הוא קטן *כרצוננו*. פירוש הדבר הוא שאפשר, באמצעות הגדלה לא משמעותית של זמן הריצה, להקטין משמעותית את ההסתברות לטעות. במקרה של מילר רבין, כל "בדיקה" שהאלגוריתם מבצע מותירה הסתברות של 1/4 לטעות (רק אם המספר לא ראשוני; אם הוא ראשוני, האלגוריתם תמיד מצליח). פירוש הדבר הוא שאחרי שתי בדיקות ההסתברות לטעות תהיה 1/16, אחרי שלוש, 1/64, ובאופן כללי - כל נסיון נוסף מקטין את ההסתברות לטעות פי 4. מהר מאוד אפשר להגיע להסתברויות נמוכות בצורה קיצונית לטעות - ההסתברות שמשהו יתפקשש בחומרה עצמה כבר תהיה גדולה יותר. אם בטעות מיוצר מספר לא ראשוני, אז יש סיכוי לא רע שזה יתגלה כבר בהצפנות הראשונות, בגלל שיהיה קושי לפענח חלק מההודעות (לא את כולן), אז תמיד אפשר לעשות כמה הרצות מבחן ולראות מה קורה. מה שחשוב להדגיש בכל הסיפור הזה הוא שייצור המפתח של RSA הוא דבר די חד פעמי, ולכן אפשר להקדיש לו המון זמן. תקשורת שוטפת מוצפנת בעזרת שיטות הצפנה סימטריות (שהן מהירות הרבה יותר מ-RSA), וה-RSA משמש רק להחלפה בטוחה של מפתחות אקראיים עבור השיטות הללו. |
|
|
|
|
|
|
||
|
||||
|
הנה רעיון נחמד להבטיח שההצפנה תמיד תעבוד, גם אם המספרים אינם ראשוניים: כאשר אתה מריץ את מבחן מילר-רבין, תבדוק את כל הראשוניים הקטנים (נניח ה- 64 הראשונים). אח"כ תקודד את ההודעה שאתה רוצה לשלוח באמצעות הכפלה או אי הכפלה בראשוני הקטן המתאים (אתה שולח 64 ביט להודעה במקום, נניח, 512, כי כל ביט עולה לך יותר מביט בשידור, אם אתה רוצה שהמודולו לא ייכנס לפעולה כדי שהצד השני יוכל לשחזר את החזקות בצורה טריביאלית). מכיוון שבדקת עבור כל הראשוניים הנ"ל שכל אחד מהם בחזקת p-1 שווה ל- 1, מובטח לך שזה יקרה גם למכפלה כלשהי שלהם (וגם ל- q, וגם ל- pq). השימושיות של הרעיון היא כמובן נמוכה מהשימושיות של אלגוריתם דטרמיניסטי לראשוניות (יש שיגידו שהשימושיות היא שלילית, כי באלגוריתם המקורי לפחות יש סיכוי שתוך כדי השימוש השוטף תגלה שמשהו לא בסדר, בעוד שפה אתה טומן את הראש בחול), אבל זה עדיין רעיון נחמד לדעתי. אגב, כדאי לציין שלפעמים, במקום להשתמש ב- RSA כדי *להעביר* מפתח מצד א' לצד ב', אפשר להשתמש פרוטוקול דיפי-הלמן [ויקיפדיה] כדי *לתאם* מפתח בין שני הצדדים (כלומר, זה לא שמישהו בוחר את המפתח ואז מעביר אותו לשני; משתמשים בפרוטוקול שבסופו יש לכל אחד מהצדדים מפתח, שאף אחד מהם לא בחר, ושלא ידוע לאף אחד אחר מלבדם). |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי שום דבר מהרעיון, אני חושש. דיפי הלמן זה סיפור בפני עצמו. כמובן שזו שיטה מקסימה, ויש לה שימושים פרקטיים רבים; אבל יש לה את הסכנות שלה (בפרט, היא חשופה בצורה קיצונית למתקפת Man-in-the-middle). כשמגיעים לשימושים מעשיים, לרוב מה שיש הוא מיש-מש אחד גדול של הרבה שיטות. למשל, פרוטוקול IKE שמשמש להסכמה על מפתח הצפנה (סימטרי) משותף משתמש גם בדיפי הלמן כדי לייצר סוד משותף, וגם (באחד מאופני התפעול שלו) בחתימות מבוססות מפתח פומבי כדי למנוע את המתקפות הסטנדרטיות על דיפי-הלמן. |
|
|
|
|
|
|
||
|
||||
|
ניקח מספר "חשוד כראשוני" p. נבדוק האם כל המספרים 2,3,5,7 ועד הראשוני ה- n מקיימים n^(p-1)=1 מודולו p. נוודא שאותו דבר מתקיים עבור מספר "חשוד כראשוני" q. נוודא גם שמכפלת כל n המספרים האלו קטנה מ- pq. כעת, נניח שאנחנו רוצים להעביר הודעה בת n ביטים. נקודד את ההודעה באמצעות מספר שמהווה את מכפלת כל הראשוניים שעבורם הביט הוא 1 (ניסוח שקול: נעלה כל ראשוני בחזקת הביט שלו ונכפיל). נקרא למספר הנ"ל A. נשים לב ש- A מקיים בהכרח A^(p-1)=1 מודולו p וכנ"ל עבור q, כי A הוא מכפלה של מספרים שמקיימים תנאי זה. נצפין את ההודעה "בדרך הרגילה". הפענוח "בדרך הרגילה" בהכרח ייתן את המספר A. מכיוון שמכפלת כל n הראשוניים היתה קטנה מ- pq, בהכרח כך גם A, שהוא מכפלה של קבוצה חלקית שלהם. לכן, הצד המפענח יכול פשוט לבדוק אם A מתחלק ב- 2,3,5 וכו', ולקבל את n ביטי ההודעה המקוריים. כמובן שהשיטה בזבזנית, כי כדי להעביר הודעה של n ביטים היינו צריכים להעביר הודעה של יותר ביטים. אפשר לייעל ע"י כך שלמספרים קטנים יותר נרשה חזקות גדולות יותר (באמת מעניין לחשב כמה מידע אפשר לשדר בדרך זאת עם, נניח, מספר pq של 1024 ביט). חסרון נוסף של השיטה הוא כמובן שאנחנו סתם יורים לעצמנו ברגל: לו היינו מצפינים הודעות רגילות, ואחד המספרים (p או q) לא היה ראשוני (אלא "במקרה" עבר את המבחנים שלנו), היה סיכוי שנצפין הודעה "רעה" והפענוח ייתן הודעה שונה. כך היינו עולים על הבעיה. השיטה הזאת מבטיחה שלא נעלה על הבעיה, וזה לא כל כך חכם. מה שאהבתי בדיפי הלמן זה את האפשרות לתאם מפתח מבלי שאף אחד "תכנן" את המפתח הזה. אני לא מכיר פרוטוקולים "אמיתיים", אבל אם הייתי מתכנן אחד אני מניח שהייתי משתמש בשילוב של כמה שיטות . |
|
|
|
|
|
|
||
|
||||
|
אני עדיין לא מבין. הבנתי את הרעיון הבסיסי, אבל לא למה זה עובד. אתה אומר "נצפין בדרך הרגילה" ו"נפענח בדרך הרגילה" - אבל איך אתה עושה את זה? כדי לבנות מפתחות הצפנה ופענוח שעובדים, אתה צריך לדעת את פונקצית אוילר של pq; כדי לדעת אותה, אתה צריך לדעת את p,q *ולדעת שהם ראשוניים*. אם הם לא ראשוניים, אנחנו באותו ברוך כמו כל מי שמנסה לפרוץ מבחוץ; החישוב של פונקצית אוילר של מספר קשה בדיוק כמו הפירוק שלו לגורמים. אז מה שקורה (לדעתי; לא בדקתי אף פעם מימוש "אמיתי" של RSA) הוא שמחשבים את פונקצית אוילר פשוט בעזרת הנוסחה (p-1)(q-1) שנכונה רק עבור ראשוניים. אם אין לך ראשוניים, תקבל d שייתכן מאוד שלא יעבוד (עשיתי כמה ניסויים עצמיים בזה - מקבלים d שלפעמים עובד ולפעמים לא). אני לא רואה למה השיטה שאתה מציע פותרת את הבעיה הזו (כמובן שייתכן שהיא פותרת ואני פשוט מפספס את החשבון).
|
|
|
|
|
|
|
||
|
||||
|
אז השיטה ברורה. עכשיו רק נשאר להסביר למה היא עובדת. אם כן, נניח שעבור A מסוים אנחנו יודעים ש- A^(p-1)=1 מודולו p, וש- A^(q-1)=1 מודולו q. עכשיו, את מפתחות ההצפנה והפענוח d,e בונים כך שיתקיים de=1 מודולו (p-1)(q-1). אם ההודעה המקורית היתה A, ההודעה המפוענחת תהיה A^de. נבדוק מה קורה מודולו p ומודולו q בנפרד. מודולו p: A^(de) = A^(k*(p-1)*(q-1)+1) = (A^(p-1))^(k*(q-1))*A = 1^(k*(q-1))*A = A ואותו הדבר מודולו q. ממשפט השאריות הסיני(1) נובע שנקבל חזרה את A, ולכן הפענוח יצליח.----------------- (1) עכשיו שמתי לב שבעצם יש פה דרישה נוספת - ש- p ו- q יהיו זרים (כלומר, אם במקרה נפלנו בשניהם על מספרים פריקים, ואם במקרה שני המספרים הפריקים אינם זרים זה לזה - נדפקנו). אפשר פשוט לוודא שהם זרים (אלגוריתם GCD הוא פולינומיאלי בגודל הקלט). לחליפין, אפשר לפתור בדרך אחרת: במקום לבדוק ש- 2,3,5 וכו' עוברים את מבחן פרמה, תבדוק ש- a^de=a מודולו pq, עבור כל המספרים האלו. אז מובטח לך שזה יהיה נכון גם עבור כל מכפלה שלהם. |
|
|
|
|
|
|
||
|
||||
|
אחלה. עכשיו אני נוטה להסכים שמדובר בשיטה לא משהו, אבל שהיא עובדת. | |
|
|
|
|
|
||
|
||||
|
אני בטוח שאחרי השרשור הזה נחה דעתו והתבססה הבנתו של מוס גולמי :-) | |
|
|
|
|
|
||
|
||||
|
לדעתי נחה הבנתו (היא לא התקדמה לשום מקום) והתבססה דעתו (על משתתפי הדיון). | |
|
|
|
|
|
||
|
||||
|
אפשר לקבל דוגמא לבעיה שהיא *לא* NP? תודה |
|
|
|
|
|
|
||
|
||||
|
כל הבעיות ב-NP הן כריעות. לכן, בעיות שאינן כריעות הן לא NP. לכן (לדוגמא) בעיית העצירה [ויקיפדיה] היא לא ב-NP. | |
|
|
|
|
|
||
|
||||
|
זו דוגמא טריוויאלית מדי. אני רוצה בעיה *כריעה* שלא נמצאת בNP. | |
|
|
|
|
|
||
|
||||
|
באמת מעניין. כל חומר הקריאה שלי בנושא חוזר ומזכיר שיש כאלה (בעיות ספירה?), אבל הטקסט מציין כדרך אגב ש"נהוג להאמין שהבעיה לא ב-NP" או "סביר להניח שאיננה ב-NP" או ש"ההוכחה לכך שבעיה זו איננה ב-NP איננה פשוטה". גדי? |
|
|
|
|
|
|
||
|
||||
|
ידוע שהמחלקה EXSPACE (בעיות שניתן לפתור עם מכונת טיורינג עם מקום אקספוננציאלי באורך הקלט) מכילה ממש את NP. לכן בעיות שלמות ב-EXSPACE אינן ב-NP. לדוגמאות לבעיות כנ"ל ראה http://en.wikipedia.org/wiki/EXPSPACE |
|
|
|
|
|
|
||
|
||||
|
ב-Complexity zoo 1 אפילו כותבים דוגמה קונקרטית: "The theory of reals with addition (see EXPSPACE) is hard for NEXP" ההפניה שהם נותנים היא ל:M. J. Fischer and M. O. Rabin. Super-exponential complexity of Presburger arithmetic, Complexity of Computation (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974. ואני עצמי לא מסוגל (כרגע) להסביר יותר מכך.--------- |
|
|
|
|
|
|
||
|
||||
|
מה בדבר בעיית ההכרעה "לגרף הנתון אין מעגל המילטוני"? זו בוודאי בעייה ב-co-NP כי אם אין זה נכון שאין בגרף מעגל המילטוני, יש לכך הוכחה פשוטה (הנה המעגל). מצד שני, לא נראה שיש בהכרח "עד" פולינומיאלי לכך שגרף נתון *אינו* מכיל מעגל כזה. מצד שלישי, הוכחה לכך שבעייה זו באמת איננה ב-NP תהווה גם הוכחה לכך ש-NP שונה מ-co-NP, ואם אינני טועה(?) זו בעייה פתוחה הנחשבת קשה. נדמה לי שלפנינו בעייה כריעה שאיננה ב-NP (כפי שביקשת), אך איננו יודעים להוכיח שזה באמת המצב. |
|
|
|
|
|
|
||
|
||||
|
א) למעשה הבעיה הנ"ל היא co-NP שלמה, דהיינו היא (1) ב-co-NP כפי שאמרת ו-(2) היא "קשה" לפחות כמו כל בעיה ב- co-NP. על כן, לא זו בלבד שהוכחת ההשערה הנ"ל ("אין-מעגל-המילטוני אינה ב-NP") מספיקה כדי להוכיח את הטענה "NP שונה מ-co-NP ", היא גם הכרחית, כלומר, שתי הטענות הן שקולות. ב) אינך טועה זוהי בעיה פתוחה חשובה ומפורסמת, ועל פי מצב הידע הנוכחי, נראה שאנו רחוקים שנות אור מלגרד את קצה אפה של טענה כזו. |
|
|
|
|
|
|
||
|
||||
|
אני לא מכיר דוגמא "מעניינת" (אולי כי בעיה כזו הייתה כבר נזנחת מזמן). מה כן? בעיית מגדלי האנוי מובאת תמיד בתור דוגמה לבעיה שהפתרון שלה (רשימת הצעדים שצריך לבצע כדי לפתור את המגדל) יהיה אקספוננציאלי בהכרח. כמובן שזה "לא מעניין" כי כאן ידוע בדיוק איך לפתור ורק ביצוע הפתרון עצמו הוא אקספוננציאלי. יש מה שנקרא "משפטי היררכייה" לסיבוכיות שמבטיחים קיום בעיה שאפשר לפתור רק בסיבוכיות (זמן/זכרון) גדולה כרצוננו, כל עוד הפונקציה היא "נורמלית" (2 בחזקת n זו פונקציה נורמלית, לצרכנו). ההוכחה היא בשיטת לכסון ובאופן כללי לא נותנת ביד שום בעיה ידועה ומעניינת. TQBF [Wikipedia] היא בעיה חביבה למדי שמאוד לא סביר שתהיה ב-NP, אבל לא באמת ידוע; היא מה שנקרא PSPACE-שלמה, שזה כמו NP-שלמה רק עבור מחלקה (כנראה) גדולה יותר, של כל הבעיות שאפשר לפתור בסיבוכיות *זכרון* פולינומית. היא די דומה באופיה ל-SAT, למי שמכיר, רק שכאן יש לנו נוסחה בתחשיב *הכמתים*. כאמור, ייתכן ש-P=PSPACE ואז בפרט זו בעיית NP; אבל זה מאוד מאוד לא סביר. מקום טוב אחד להתחיל לחפש בו דוגמאות לבעיות קשות "ממש" הוא "אלגוריתמיקה" של דוד הראל, שלצערי לא לידי כרגע. |
|
|
|
|
|
|
||
|
||||
|
אהבתי במאמר שלך את תמונת החרוזים |
|
|
|
|
|
|
||
|
||||
|
חשבונייה, קראו לזה פעם. | |
|
|
|
|
|
||
|
||||
|
והנה אתר שמוקדש לו: http://www.ee.ryerson.ca/~elf/abacus/ | |
|
|
|
|
|
||
|
||||
|
בהמשך לדיון על אאופמיזם: זו לא מילה אנגלית! זו מילה לטינית, ממקור יווני עם ניחוח שמי, והיא משותפת לכל שפות אירופה. די לאנגלוצנטריות! | |
|
|
|
|
|
||
|
||||
|
פשוט מקורה בלטינית (לא כתבתי בשום מקום שזו מילה *רק* באנגלית). | |
|
|
|
|
|
||
|
||||
|
קראתי פעם שמקורה במלה ''אבק''. | |
|
|
|
|
|
||
|
||||
|
זאת אומרת, אם מאמינים לזה: או שמא בפיניקית: |
|
|
|
|
|
|
||
|
||||
|
סוף סוף קצת כבוד לקומבינטוריקה. והנה קצת מספרים: |
|
|
|
|
|
|
||
|
||||
|
...ועדי שמיר זכה בפרס למדעי המחשב (טיפה יותר רלוונטי, למרות שגם הזכייה של אלון בעיקר מעוררת את השאלה ''מה לקח להם כל כך הרבה זמן''). | |
|
|
|
|
|
||
|
||||
|
סופר לי מפי קולגה שברדיו, כשדיווחו על הפרס, התייחסו שוב ושוב לעבודתו של ''פרופ' נוגה''. | |
|
|
|
|
|
||
|
||||
|
כמו Sir Paul | |
|
|
|
|
|
||
|
||||
|
נוגה זה לא שם המשפחה שלו? | |
|
|
|
|
|
||
|
||||
|
לא, זה שמו הפרטי הנוגה. | |
|
|
|
|
|
||
|
||||
|
דווקא נוגה אלון יותר רלוונטי לתיאוריה של מדעי המחשב. הדירוג שהבאתי למעלה (נוגה אלון ממוקם שני במדעי המחשב בכל הזמנים וראשון בועידות התיאוריה) מבוסס, משום מה, על אלגוריתם דמוי page rank של גוגל, על גרף מחברי המאמרים המשותפים. |
|
|
|
|
|
|
||
|
||||
|
למה "מישום מה"? ככה מעריכים אקדמאים כבר מאות שנים. חוקר מוכשר הוא חוקר שחוקרים מוכשרים חושבים שהוא מוכשר. לגבי גדולים בתורה, אגב, זה מאוד דומה. | |
|
|
|
|
|
||
|
||||
|
מדובר על אנשים שיש להם הרבה שיתופי פעולה, לא הרבה ציטוטים. | |
|
|
|
|
|
||
|
||||
|
הוכחות לכך ש-P שונה מ-NP, שווה לו או שבכלל הבעיה אינה כריעה הן דבר די נפוץ, אבל הרבה פחות נפוצות הוכחות שנראה על פניו שיש בהן משהו ומעוררות התרגשות בקהילה, ועושה רושם שצצה עכשיו אחת כזו. מצד אחד: ומצד שני, פחות אופטימי: בכל מקרה יהיה מעניין לעקוב ולראות מה קורה עם זה. לתוהים - לא, הוכחה לא תגרום לשינוי מהותי במדעי המחשב (להבדיל ממה שהוכחה ש-P=NP הייתה גורמת), אלא בעיקר לאישוש של מה שכולם בטוחים שהוא נכון וכנראה לקידום טכניקת ההוכחה ולשימושים נוספים שלה. מצד שני, זה עדיין פתרון של חידה עתיקה יחסית בענף וההתרגשות מוצדקת. |
|
|
|
|
|
|
||
|
||||
|
עדכון: חוות הדעת הנוכחית שכמה מהשמות הגדולים מביעים בבלוגים שבהם מתקיים דיון בנושא - ההוכחה לא עובדת, לא ניתן לתקן אותה, ואין בה רעיונות חדשים טובים שאפשר להשתמש בהם בכל זאת. חבל. |
|
|
|
|
|
|
||
|
||||
|
הוכחה ש-P שונה מ-NP? אולי. פרטים אחדים כאן: http://www.gadial.net/?p=696 | |
|
|
|
|
|
||
|
||||
|
פרטים נוספים, אצל גדי אלכסנדרוביץ': תגובה 547997. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ב-1979 התפרסמה בניו יורק טיימס ידיעת מדע פופולרי קצרה מאת אחד מלקולם בראון, על התפתחות במחקר איפשהו בין אופטימיזציה לחישוביות. מדען המחשב קריסטוס פפדימיטריו התעצבן על אי-הדיוקים שהסתננו לכתבה, ואחד התרגילים בספר שלו Combinatorial Optimization: Algorithms and Complexity כולל את הידיעה במלואה, לצד המטלה: Determine, when possible, whether each statement is (a) true, (b) false, (c) misleading, (d) equivalent to a well-known conjecture, the solution of which was probably not known to Mr. Browne. אותי זה הצחיק.
|
|
|
|
|
|
|
||
|
||||
|
אני אוהב מאוד כתבות כאלו כי הן מספקות חומר בלתי נלאה לבלוג. אולי אציע לצוות של קריפטו הסמסטר לעשות תרגיל דומה עבור הכתבה הזו: (בונוס מיוחד יינתן לסטודנטים שישימו לב לכך ששפי גולדווסר זו "היא"). |
|
|
|
|
|
|
||
|
||||
|
אני מקווה שלא אכפת לך שהשתמשתי בזה כאן. | |
|
|
|
|
|
||
|
||||
|
נהפוך הוא, לכבוד לי. | |
|
|
|
|
|
||
|
||||
|
אם אתה עדיין אוסף ציטוטים משעשעים מספרי מתמטיקה, יש לי עוד שניים בשבילך. המתמטיקאי דייוויד בנסון כתב ספר נפלא על מוזיקה ומתמטיקה, שזמין להורדה בחינם ובאופן חוקי מהאתר שלו1. בעמ' 45 הוא מתאר את תופעת גיבס - "בעיה" בהתכנסות של טורי פורייה סמוך לנקודות אי רציפות עם קפיצה, שמתבטאת ב-overshoot של כ-8.9% מגודל הקפיצה. בהערת שוליים למספר הנ"ל הוא כותב שהערך חושב לראשונה ע"י Maxime Bocher ב-1905, ומוסיף: "A number of otherwise reputable sources overstate the size of the overshoot by a factor of two for some reason probably associated with uncritical copying." בעמ' 73 בנסון מתאר את פונקציית הדלתא של דיראק, ששונה מ-0 רק בנקודה אחת, אבל הערך שלה בנקודה הזו כל כך גדול עד שהאינטגרל סביבה הוא 1. על צירוף הדרישות הנ"ל הוא כותב:"The awake reader will immediately notice that these properties are contradictory." בהמשך הוא כמובן מסביר איך ליישב את הסתירה.___________ 1. מומלץ ביותר. הספר מונח בקביעות מזה שנים ליד המיטה שלי, ואני שוב ושוב נהנה לחזור אליו ולגלות (או לגלות מחדש) פינות נהדרות |
|
|
|
|
|
|
||
|
||||
|
גם אז לא אספתי ציטוטים, פשוט נתקלתי בשאלה ב-mathoverflow. בכל אופן, הספר נראה מענין, נראה אם הוא אכן מענין. | |
|
|
| חזרה לעמוד הראשי | |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |