P=NP?

[vizini]

P=NP?

מישהו רוצה להגיב על המאמר הזה? זו בדיחה או שזה אמיתי?

 

[BanjoKazooie]

לא שהבנתי את ההוכחה

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

 

[Joe0077]

לא קורא תהוכחה

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

 

[freedom rider]

../images/Emo45.gif

 

[vizini]

ראשית, זה לא "עמוד נידח ברשת".

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

 

[bralon1]

לא רק מיטב החוקרים יש גם מתחזים

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

 

[IsraeliSecretToilets]

מאמר הזוי ../images/Emo12.gif

והוא לא שכנע אותי ש- P=NP.

 

[טלמון סילבר]

מה זה בכלל P=NP ?

 

[IsraeliSecretToilets]

אממ..

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

 

[BanjoKazooie]

לפי דעתי צריך להוסיף את זה לשאלות

נפוצות

 

[IsraeliSecretToilets]

עוד משהו חשוב..

קיימת תת קבוצה של בעיות NP הנקראת NP-Complete. בעיה A השייכת ל-NP-Complete מקיימת את ההגדרה הבאה: 1) הבעיה נמצאת ב-NP 2) לכל בעיה אחרת ב-NP אפשר לעשות רדוקציה שפועלת בזמן פולינומיאלי לבעיה A. מאמינים שמחלקת בעיות זו היא המפתח לפתרון הבעיה האם P=NP. זה נכון בגלל המשפט הבא: אם L שייכת למחלקה NP-Complete וגם L שייכת למחלקה P אזי P=NP. המשפט נכון מפני שאם L שייכת למחלקה P אז יש לה פתרון דטרמיניסטי בזמן פולינומיאלי. ולכן אם ניקח כל בעיה אחרת M ב-NP נעשה לה רדוקציה בזמן פולינומיאלי לבעיה L, נפתור את L ונקבל פתרון בזמן פולינומיאלי לבעיה M. ולכן כל בעיה M השייכת ל-NP ניתנת לפתרון בזמן פולינומיאלי. נכון להיות ידועות כמה מאות בעיות השייכות למחלקה NP-Complete ולאף אחת מהן לא נמצא פתרון הפועל בזמן פולינומיאלי. Independent Set היא אחת מהבעיות האלה, ואפשר להוכיח את זה מתמטית (למעשה, היה לי להוכיח את זה מתמטית בתרגיל בית במודלים חישוביים

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

).

 

[טלמון סילבר]

../images/Emo51.gif מעולם לא עסקתי

בתחום זה, אפילו לא בסביבתו הקרובה

 

[IsraeliSecretToilets]

זה בסדר..

חישוביות/סיבוכיות זה לא תחום כזה מעניין. למען האמת אנחנו כמעט נרדמנו בהרצאות במודלים חישוביים

 

[קפטן ברני]

חבל שגילית לו...

לרגע אחד ידעתי משהו שטלמון לא. למה הרסת?

(טלמון, קח את זה כמחמאה)

 

[amirb7]

רגע! אם P=NP אי אפשר לצמצם P ??

ואז נקבל N=1. מ.ש.ל אולי מישהו מוכן לסכם בכמה משפטים את רעיון ההוכחה במאמר שהובא לעיל? אולי מביא המאמר הנ"ל מוכן לקחת את המשימה על עצמו? במיוחד כיוון שהוא פיזיקאי ...

 

[אוֹריארד]

תראה... ../images/Emo26.gif

אני לא מכיר אותו אישית, אבל אולי P הוא סתם אפס?...

 

[the another one]

אל תדאג, אני אמסור לו שאמרת את זה.

.... בעצם, אני אחכה שהוא ישתחרר מהכלא...

 

[the new L]

עד כמה שהבנתי

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

 

[amirb7]

../images/Emo45.gif עכשיו הבנתי, תודה!

 

[דודהלי]

דבר בשם עצמך!!! ../images/Emo46.gif

לדעתי חישוביות זה אחד התחומים היותר מעניינים שקיימים במדעי המחשב, ואפילו טרחתי לכתוב תיזה בתחום הנפלא הזה!