בתשובה לשוטה הכפר הגלובלי, 16/08/10 11:11
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"? אני עוד מפסיד עליך פה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות