בתשובה להאייל האלמוני, 25/12/06 11:31
 |
|
 |
||
|
||||
 |
בקשר לסיבוכיות - אני בהחלט אנסה להתייחס לזה במאמר הבא. בעיקרון, הסיבוכיות מאוד תלויה במודל שבו משתמשים. אחת הסיבות שבגללן משתמשים בסיבוכיות פולינומית כדי לציין סיבוכיות "טובה" היא שההגדרה הזו מבטיחה תלות נמוכה למדי במודל - אלגוריתם שהוא פולינומי במכונת טיורינג "פושטית" יהיה פולינומי (עם פולינום אחר) גם במכונת טיורינג עם מאה סרטים, וכו'. אלא שיש מקומות שבהם שינוי המודל כבר גורר כמעט בהכרח שינוי בסיבוכיות. הבעיה של P=NP היא בדיוק דוגמה לכך - אם אנחנו מוסיפים למכונה אי דטרמיניזם, כבר לא ברור לנו האם בעיה שהיא פולינומית במכונה האי דטרמיניסטית היא בהכרח גם פולינומית במכונה הדטרמיניסטית (וזאת להבדיל משאלת הכריעות - מכונת טיורינג דטרמיניסטית שקולה לאי דטרמיניסטית בכל הנוגע לשאלה האם ניתן להכריע בעיה מסויימת או לא). עוד דוגמה: יש קישור למאמר של איזי למעלה. במאמר הזה מתוארים "אלגוריתמים קוונטים". אני לא מתמצא בתחום הזה, אבל למיטב הבנתי גם במקרה הזה מדובר על מודל חזק יותר של מכונת טיורינג, שיכול לפתור בעיות מסויימות (כמו פירוק לגורמים) הרבה יותר מהר ממכונה רגילה. החשיבות של האלגוריתמים הללו היא שבניגוד למכונה אי דטרמיניסטית, חושבים שניתן יהיה לממש מכונה קוואנטית שמריצה אותם בפועל. בקיצור, סיבוכיות הוא תחום מסובך, ואני לא מכיר אפילו את קצה הקרחון שלו. |
 |
 |
 |
|
|
|
||
|
||||
|
אגב, סקוט ארונסון מציע השערה שקצת מזכירה את תיזת שכ"ג-עמית: The NP Hardness Assumption: There is no physical means to solve NP-complete problems in polynomial time. לשאר ההרצאה המשעשעת: |
|
|
|
|
|
|
||
|
||||
|
מה זה ה-NP הזה, במטותא? | |
|
|
|
|
|
||
|
||||
|
עכש"י זה קבוצת כל השאלות (החישוביות) שאפשר לוודא(או לפסול?) פיתרון משוער שלהן בזמן חישוב פולינומיאלי ( כלומר חזקה של אורך השאלה) | |
|
|
|
|
|
||
|
||||
|
תודה. נניח שהבנתי:). אבל אם כך, מה זה P=NP? | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
מאמר נחמד מאוד! (אפשר לשאול מהי תיזת שכ"ג-עמית? יש לי קשר לזה?) |
|
|
|
|
|
|
||
|
||||
|
תיזת שכ"ג עמית: אין דרך פיסיקלית להבחין בין החלטה חופשית להחלטה אקראית. תגובה 423933 |
|
|
|
|
|
|
||
|
||||
|
ואללה? אני בקושי זוכר ששוחחתי עם שכ"ג על העניין הזה, אך בכל אופן אני מסכים עם עצמי-מלפני-כמה-זמן-בשיחה-עם-שכ"ג: ודאי שאין דרך *אמפירית* להבחין (אצל מישהו אחר) בין החלטה "חופשית" להחלטה מוכתבת אלגוריתמית עם מרכיבים אקראיים. הייתי בטוח שזה, לפחות, מוסכם על כולם (אפילו על המתווכחים ומתווכחות עם שכ"ג בלהט). | |
|
|
|
|
|
||
|
||||
|
אליבא דדב אנשלוביץ והמקור בר-הסמכא שלו זה בכלל לא מוסכם (אלא אם כן אני לא מבין מה הוא אומר). (לא שוחחת. כתבת מכתב, בסמוך לפרסום המאמר שלי, ובו אמרת משהו ברוח הזאת) |
|
|
|
|
|
|
||
|
||||
|
חשבתי שהמקור בר-הסמכא הוכיח שאי-שוויון בל מוכיח שיש בחירה חופשית או משהו כזה. זה נותן גם מבחן אמפירי? (כן, לזה התכוונתי. אני מרבה לשוחח בתקתוק). |
|
|
|
|
|
|
||
|
||||
|
טענת המקור של דב היא הרבה יותר צנועה, ולא *לחלוטין* נטולת בסיס: שללא הנחת בחירה חופשית, אי אפשר להסיק את המסקנות הידועות מניסוי בל. | |
|
|
|
|
|
||
|
||||
|
תגובה 229301 | |
|
|
|
|
|
||
|
||||
|
צודק: תיזת שכ"ג עמית מיסודו של איזי. | |
|
|
|
|
|
||
|
||||
|
אני מתנצל. כל השיחה ההיא נשכחה ממני. | |
|
|
|
|
|
||
|
||||
|
אלא אם כן הן אותו הדבר (תגובה 56073 מדהים כמה האייל נשאר במקום)... | |
|
|
|
|
|
||
|
||||
|
רק להבהיר, לא ידועה כיום אף בעיה ב NP-Complete שיש לה אלגוריתם פולינומיאלי במודל של חישוב קוואנטי. בפרט, אין הוכחה שמודל החישוב הקוונטי חזק יותר ממכונת טיורינג קלאסית. | |
|
|
|
|
|
||
|
||||
|
כמובן. תודה על התיקון. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |