טרחנים כפייתיים במתמטיקה

בתשובה לדרור, 12/08/10 1:15

P!=NP

548639

אריה • בתשובה לדרור

יום א', 15/8/2010, 17:23

ואם יסתבר שיש בסוף טעות בהוכחה שלו
האם מחבר המאמר יחשב לטרחן מתמטי ?

P!=NP

548641

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום א', 15/8/2010, 18:04

לא.

P!=NP

548643

אריה • בתשובה לגדי אלכסנדרוביץ'

יום א', 15/8/2010, 18:15

מדוע לא?

P!=NP

548644

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום א', 15/8/2010, 18:21

מדוע כן?

בוא נלך לפי ה"הגדרה" של אלון:

"...השרויים בשכנוע עמוק שביכולתם לעשות דבר־מה שהוכח כבלתי־אפשרי (כמו למצוא נוסחה למשוואות ממעלה חמישית), או שבידיהם פתרון קצרצר לבעיה קשה ביותר (כמו משפט ארבעת הצבעים), או שהם זיהו טעות יסודית שכולנו, שוטים שכמונו, הרשינו למורינו לבלבלנו באמצעותה (למשל, ש- 0.9999 =1). לעיתים קרובות הם חשים שתגליתם המרעישה יש בה כדי לחולל מהפכה מוחלטת בחשיבה המדעית, ממכניקת הקוונטים ועד לסוציולוגיה. ומובן שנלווית גם תיאוריית הקשר: הממסד המדעי מתנכר להם מסיבות מסתוריות, ומונע מהם את ההכרה והיוקרה שהם זכאים לה."

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

אנשים שטורחים ועומלים על בעיה מתמטית קשה מתוך היכרות ובקיאות בנשוא הם לא טרחנים. גם כשהם טועים.

P!=NP

548653

אריה • בתשובה לגדי אלכסנדרוביץ'

יום א', 15/8/2010, 19:54

הבנתי.האם המסקנה השלילית של הבודקים להוכחה היא סופית?

P!=NP

548656

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום א', 15/8/2010, 19:58

המסקנה שלהם? כן. אבל זה עוד לא סוף הסיפור, כי אפשר לצפות לתגובה של כותב ההוכחה ולגרסה הסופית שלו (כל הדיון התרחש סביב טיוטה לא סופית, למיטב הבנתי). עם זאת, אני לא אופטימי.

P!=NP

548678

אריה • בתשובה לגדי אלכסנדרוביץ'

יום א', 15/8/2010, 23:48

האם יכול לקרות מה שקרה עם ההוכחה של משפט פרמה שהתגלה איזה חור בהתחלה ואחר כך זה תוקן ?

P!=NP

548690

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 8:54

לא נראה שזה המצב כאן (מן הסתם מבקרי ההוכחה מתייחסים לאפשרות הזו). למשל, כאן:

http://rjlipton.wordpress.com/2010/08/11/deolalikar-...

שים לב לציטוט (באפור) של טרנס טאו.

P!=NP

548703

שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 11:11

רק בעקבות החדשות האלה תפשתי שכל מה שצריך הוא למצוא בעיה אחת (אחת!) שנמצאת ב-NP אבל לא ב-P. בהתחשב במספר הבעיות העצום משונה שזה כל כך קשה.

P!=NP

548706

גדי אלכסנדרוביץ' (אתר) • בתשובה לשוטה הכפר הגלובלי

יום ב', 16/8/2010, 11:27

אני בטוח שהיה לי פוסט כלשהו בנושא (פרצוף זועף כאן).

מספר הבעיות לא ממש רלוונטי כאן. הבעיה היא יותר כללית - במדעי המחשב לא יודעים להוכיח חסמים תחתונים. כמעט בכלל. יש תוצאה מפורסמת על כך שמיון "כללי" דורש זמן של לפחות nlogn - זו תוצאה נדירה למדי ואין רבות שדומות לה.

אתה גם יכול (וצריך) להסתכל על זה ככה - כדי להראות שבעיה היא קשה אתה צריך להראות שאין לה פתרון פשוט. בכלל. לא שהפתרון הנאיבי שחשבת עליו הוא גרוע; לא שהפתרונות המתוחכמים שמשתמשים בהם הם לא משהו; וגם טיעון בסגנון "כדי לדעת כך וכך *חייבים* קודם לעשות את..." כי ברוב המוחץ של המקרים לא באמת "חייבים", זה פשוט הדמיון הלא יצירתי שלך שגורם לך לחשוב כך. אתה חייב לתפוס איכשהו את כל הגישות האפשריות לפתרון של הבעיה - אלו שהומצאו, אלו שיומצאו בעתיד, ואלו שאף אדם לא יצליח אי פעם לחשוב עליהן מרוב שהן מסובכות, ועם זאת הן עדיין *קיימות*. זה לא פשוט בכלל.

תשאל, אם כך - איך זה שהצליחו להוכיח, ועוד בקלות, שיש בעיות שבכלל אי אפשר לפתור? ובכן, לא בדרך הזו אלא בדרך עקיפה - הראו שאם יש פתרון לבעיה מסויימת, אז קורים דברים בלתי אפשריים בעליל. כשמגבילים את עצמנו לדיבורים על P נגד NP השיטות הללו לא עובדות, וקיימת לכך אפילו הוכחה מתמטית.

P!=NP

548716

שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 13:05

מי שצריך לזעום הוא אני - על זכרוני הרופס, לא אתה.

(אני לא מנסה להגיד שהבעיה קלה, אני רק זועק את זעקת האינטואיציה: "מה כבר ביקשתי? בעיה אחת! אחת!!").

P!=NP

548725

גדי אלכסנדרוביץ' (אתר) • בתשובה לשוטה הכפר הגלובלי

יום ב', 16/8/2010, 16:03

כולנו זעקנו את הזעקה הזו מתישהו (אגב, היא עובדת אחלה גם בכיוון השני - כל מה שצריך הוא בעיה NP-שלמה אחת שנמצא לה פתרון פולינומי! אחת!)

P!=NP

623229

החוסם מטקסס • בתשובה לגדי אלכסנדרוביץ'

יום א', 6/10/2013, 1:09

החסם של nlogn למיון הוא ב"מודל ההשוואות" שהוא מודל מוגבל (אסור להסתמך על הייצוג של המספר). לא ידוע חסם תחתון סופר-ליניארי למיון במודל הרגיל של מעגלים בוליאנים (או מכונות טיורינג). בעצם, לא ידוע (לי על) חסם תחתון כזה לאף בעיה!

P!=NP

623277

אא • בתשובה להחוסם מטקסס

יום ב', 7/10/2013, 2:46

קל לחשוב על בעיה ("חשב את הייצוג האונרי של x הנתון בייצוג בינארי") שהפלט שלה סופר-לינארי, ולכן גם זמן החישוב.

P!=NP

623279

החוסם מטקסס • בתשובה לאא

יום ב', 7/10/2013, 8:38

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

P!=NP

548727

אריה • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 16:16

שמתי לב. האם טרנס טאו נחשב לבר הסמכה הגדול ?

P!=NP

548728

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 16:20

כן.

(ובעיקר אפשר לסמוך עליו שאם הוא אומר משהו שכזה, זה לא נובע מגחמה אישית שלו).

P!=NP

548739

אלון עמית (אתר) • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 17:07

(אתה מודע לכך שברגע זה זיכית את טאו באי-מייל ארוך ומפורט מאת אחד, משה קליין?)

P!=NP

548743

גדי אלכסנדרוביץ' (אתר) • בתשובה לאלון עמית

יום ב', 16/8/2010, 17:24

אני בטוח שאדם במעמדו של טאו זוכה למאות מיילים כאלו ביום.

P!=NP

548745

אלון עמית (אתר) • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 17:27

ודאי. זו לא היתה נזיפה, רק ציון עובדה.

P!=NP

548749

אריה • בתשובה לאלון עמית

יום ב', 16/8/2010, 18:03

אתה יודע לקרוא?

P!=NP

548748

אריה • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 18:02

האם תחום ההתמחות שלו במתמטיקה הוא חישוביות?

P!=NP

548754

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 18:52

לא. ואני מזהיר אותך מפני הסקת מסקנות חפוזה.

P!=NP

548758

אריה • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 20:43

בסדר. תסביר לי מדוע הבעיה הזו נחשבת להכי חשובה בתאוריה של מחשבים?

P!=NP

548760

אורי גוראל גורביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 20:50

http://www.gadial.net/?p=705

P!=NP

548770

אריה • בתשובה לאורי גוראל גורביץ'

יום ב', 16/8/2010, 21:40

גדי. האם תוכל להרחיב יותר לגבי דבריך בבלוג?:

" עם הטיעון הזה אני מסכים – כאמור, נראה לי שיש קונצנזוס רחב למדי לפיו כדי לפתור את P=NP צריך "מתמטיקה חדשה". אני פשוט לא בטוח שהתהליך שבו המתמטיקה החדשה הזו תיווצר יהיה חייב להיות איטי לפני שייקצרו הפירות. או יותר נכון – ייתכן מאוד שהמתמטיקה הזו תתפתח מבלי שנבין שהיא קשורה כלל ל-P=NP, ואז פתאום מישהו יבצע את הקישור ויוכיח "מייד" את המשפט. כמובן שייתכן שזה גם יתרחש באופן שונה; אני פשוט לא חושב שאפשר לפסול על הסף את התרחיש הזה."

P!=NP

548775

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 21:55

אני לא יודע מה עוד לומר בעניין הזה. אולי בתור דוגמת צעצוע אני יכול להביא את RSA - היעד (הצפנת מפתח פומבי) היה ידוע לכולם, אבל כדי להשיג אותו פתאום היו צריכים להשתמש בבעיה שבכלל קשורה לתורת המספרים - ומי חשב בכלל שתורת המספרים קשורה להצפנה?

(זה שקר וכזב מבחינה היסטורית, אבל כמטאפורה זה מתאים למה שאני רוצה לספר).

P!=NP

548779

אריה • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 22:07

הבנתי אותך. מחפשים להצפין עם n=pq שהוא מכפלה של 2 ראשונים גדולים. האם ניתן להבין שכדי להמציא "מתמטיקה חדשה" כדבריך, כדאי יהיה להסתכל מחדש על המספרים ?

P!=NP

548782

גדי אלכסנדרוביץ' (אתר) • בתשובה לאריה

יום ב', 16/8/2010, 22:21

לא הבנתי אותך.

(המושג שצריך יהיה "להסתכל עליו מחדש" יהיה מושג ה*חישוב*).

P!=NP

548797

אריה • בתשובה לגדי אלכסנדרוביץ'

יום ב', 16/8/2010, 23:30

הבנתי אותך. זה יפה ! - כדי להמציא "מתמטיקה חדשה" צריך להסתכל מחדש על מושג החישוב.

חזרה לעמוד הראשי

המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
RSS מאמרים \| כתבו למערכת \| אודות האתר \| טרם התעדכנת \| ארכיון \| חיפוש \| עזרה \| תנאי שימוש	© כל הזכויות שמורות