 |
|
 |
||
|
||||
 |
לאנשי מדעי המחשב: הרעיון המקורי היה שמחשב קוונטי פועל כמו "מכונת טיורינג אי-דטרמניסטית". "מכונת טיורינג אידטרמניסטית" הוא שינוי של מודל מכונת טיורינג: בכל מקום שבו המכונה נדרשת "להחליט" החישוב מתפצל למספר מסלולי חישוב שרצים במקביל. כך נוצר עץ אורך ומסועף של חישובים אפשריים. המכונה עונה "כן" אם לפחות באחד ממסלולי החישוב יש תשובה "כן". אחת ההגדרות של המחלקה NP (וזהו למעשה מקור שמה) הוא "השפות שמכונת טיורינג אי-דטרמניסטית יודעת לזהות בזמן פולינומיאלי" . כולם יודעים שעד היום לא יודעים האם P=NP, אולם ההרגשה הכללית בקרב החוקרים שזהו אי־שיוויון: מכונת טיורינג אי־דטרמניסטית יודעת לעשות דברים בזמן "סביר" שמכונה לא רגילה לא יודעת לבצע בזמן "סביר". רוב הבעיות הקשורות להצפנה שוכנות באותו מרחב שמחוץ ל־P אך בתוך NP . הסיבה לכך היא שרוצים בעיה שניתן לבדוק בה נכונות פיתרון בזמן סביר אך אין אפשרות למצוא פתרון בזמן סביר. התקווה היתה, אם כן, שמכונות קוונטיות יוכלו לבצע כל פעולה שיכולה לבצע מכונת טיורינג אי־דטרמניסטית. אולם למיטב ידיעתי היום הדעה הרווחת היא שזה לא נכון. יכול להיות שאפילו הוכיחו שאם P!=NP אז מחלקת הבעיות שניתנות לפתרון ע"י מחשב קוונטי בזמן פולינומיאלי (QP) לא כוללת את קבוצת הבעיות "הקשות" של NP (הקבוצה הידועה בשם NPC). בעיית הפירוק לגורמים, אגב, אינה בתוך NPC (בהינתן ש־P!=NP, כמובן). ר' גם: http://encyclopedia.thefreedictionary.com/computatio... |
 |
 |
 |
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ואם תצליחו להסביר לו, אשמח גם להסבר שאפילו אני אוכל להבין. | |
|
|
|
|
|
||
|
||||
|
יש תאור לא מתמטי ודי בהיר וקצר של המחשב הקוונטי בספר המצויין "סודות ההצפנה"/סיימון סינג http://www.bookme.co.il/bookdetail.asp?book_id=96038... | |
|
|
|
|
|
||
|
||||
|
לבעייה חישובית יש קלט המתאר את הבעייה, ופלט שהוא תשובה - לצורך העניין, "כן" או "לא". למשל: נתונה משוואה, האם יש לה פתרון? נתונה מפה מדינית, האם אפשר לצובעה בשלושה צבעים (כך שלמדינות שכנות צבעים שונים)? נתון מספר, האם הוא ראשוני? ככל שהבעייה "גדולה" יותר, כלומר דרושות יותר מילים כדי לתאר אותה, היא כמובן קשה יותר. יותר קשה לבדוק ראשוניות של מספר עם 1000 ספרות ממספר עם 3 ספרות. השאלה העיקרית היא, *כמה* יותר קשה הפתרון. בעייה נמצאת ב-P אם יש מספר, m, כך שהזמן הדרוש לפתרונה אינו עולה על (גודל הקלט) בחזקת m. זהו קצב גידול פולינומיאלי, הנחשב מתון: גם אם m הוא גדול, נניח 20, עדיין x^20 הוא בסופו של דבר הרבה פחות מאשר, נניח, x עצרת או שתיים-בחזקת-x. בעייה נמצאת ב-NP אם היא מקיימת תנאי (לכאורה) חלש בהרבה: אם מישהו מנחש או מציע פתרון לבעייה, דרוש זמן פולינומי כדי לבדוק אם הוא צודק. למשל, אם מישהו מציע צביעה של המפה, האם אפשר לבדוק במהירות שהצביעה היא בסדר? (כלומר, שאין זוג מדינות שכנות עם אותו הצבע). אם מישהו מציע שני גורמים של המספר, האם אפשר לכפול אותם במהירות ולבדוק שאכן יוצא המספר הנתון? בשני המקרים, התשובה היא כן. "במהירות" כאן, כמו קודם, זה "תוך זמן שאינו עולה על גודל הקלט בחזקת משהו". כמעט כל בעייה סבירה נמצאת ב-NP. לעומת זאת יש מעט מאוד בעיות שידוע שהן ב-P. כל בעייה ב-P היא גם ב-NP (אם אפשר לפתור מהר, ברור שאפשר גם לפתור מהר כשמותר לנחש). ההפתעה הגדולה היא שעד היום איש לא הצליח *להוכיח* שאיזושהי בעייה ב-NP *לא* נמצאת ב-P. (מקור השם NP, אגב, הוא Non-deterministic Polynomial. אפשר להסביר קצת יותר אם רוצים. ועוד לא דיברנו על NPC). |
|
|
|
|
|
|
||
|
||||
|
ליתר דיוק: יש הרבה בעיות ב־P . רוב האלגוריתמים שאנו משתמשים בהם בחיי היום־יום (לדוגמה: מיון, פעולות אריתמטיות) הם ב־P . אין לנו יכולת מעשית לפתור בעיות שאינן ב־BPP (אלא אם כן הקלט קטן מספיק: לדוגמה: כל מיני אתגרים לפיקטור מספרים בני בערך 500 סיביות) | |
|
|
|
|
|
||
|
||||
|
איני מסכים. מספר הבעיות שידוע שהן ב-P הוא זעום לעומת מספר הבעיות ב-NP. כמעט כל בעייה שצצה בחיי היום-יום בתורת-הגרפים, ביולוגיה חישובית, אנליזה נומרית או גרפיקה חישובית וכו' היא ב-NP, ולעיתים נדירות מאוד ב-P. האלגוריתמים בהם *משתמשים* בחיי היום יום הם, מטבע הדברים, ב-P, כי אלגוריתמים לא פולינומיאליים הם בד"כ איטיים להחריד. ה*בעיות* בהן נתקלים הן כמעט תמיד ב-NP ולא (ככל הידוע) ב-P. ה"פרדיגמה" הגדולה ב-P היא תכנון לינארי. חלק ניכר מהבעיות ב-P הן שם כי ניתן להציגן כבעיות תכנון לינארי. פרט לזאת יש די מעט אלגוריתמים פולינומיאליים מבריקים (בדיקת ראשוניות היא הילד החדש בבלוק, אבל גם קודם היה ידוע שהיא "כמעט" ב-P). |
|
|
|
|
|
|
||
|
||||
|
תוכל בבקשה להסביר בשורה או שתיים מה זה "תכנון לינארי" או להפנות למקום שמסביר? בפעם האחרונה שנתקלתי בזה, זה היה בהקשר של תורת המשחקים, וגם אז רק שמעתי שמוכיחים איתו משפט (המינימקס של פון-נוימן, אם אני זוכר נכון), לנו הוכיחו את המשפט הזה עם קבוצות קמורות. | |
|
|
|
|
|
||
|
||||
|
למיטב ידעתי: "בעיות תכנון לינארי" הן כל בעיות האופטימיזציה של פונקציה לינארית תחת אילוצים ליניאריים. זהו מקרה פרטי שימושי במיוחד של התחום הכללי שעוסק באופטימיזציה בתחומים קמורים (אילוצים ליניאריים יוצרים בהכרח תחום קמור). מה קורה עם שאר התחומים? לאלון ועוזי הפתרונים. הסיבה שבעיות כאלה חשובות, היא כי מסתבר שהמון בעיות אחרות ניתנות לניסוח כבעיות תכנון לינארי (ברשתות זרימה, בחקר ביצועים, בתורת המשחקים כמו שאמרת...). איפשהו בשנות החמישים בחור בשם ג'ורג' דנציג פיתוח אלגוריתם לפיתרון שלהן למען הצבא הבריטי (אלגוריתם הסימפלקס). אומנם אין לו חסם אסימפטוטי פולינומיאלי, אבל נדמה לי שברוב המיקרים "הישומיים" הוא יעיל מאד ולכן נמצא גם היום בשימוש נרחב (זאת, והעובדה שהוא מאפשר ניתוח רגישות פשוט, עובדה חשובה מאד בעולם האמיתי, כך סיפרו לי), למרות שפותחו אלגוריתמים נוספים ופולינומיאלים לפיתרונן (הסימפלקס הוא אלגוריתם on-boundry - כלומר הולך ומתקרב לאופטימום על פני שפת תחום האילוצים, בעוד שהאלגוריתמים הפולינומיאלים הם in-boundy, ומתקרבים לאופטימום מתוך תחום האילוצים). אני, בכל אופן, נתקלתי רק בסימפלקס (קיימים לו גם ויראציות שונות, אשר יעילות יותר בצורות מיוחדות של בעיות תכנון ליניארי). ודעה אישית לסיום: כל זה מאד מאד משעמם, אפילו שזה מתמטיקה. |
|
|
|
|
|
|
||
|
||||
|
זיכרון מעורפל מנצנץ במוחי מהקורס בחישוביות וטוען שדווקא נמצא חסם לסימפלקס. (O(n^3 אם אני זוכר נכון. | |
|
|
|
|
|
||
|
||||
|
הזכרון מוטעה. ההסבר של הילדה די מדויק (למעט זה שאני לא בטוח שאפשר לתאר את אלגוריתם האליפסואיד כ in-boundary). יש כל מיני תוצאות חיוביות על הסימפלקס כולל הוכחה שהוא רץ בזמן פולינומי על קלטים שעשו להם פרטרובציה קלה. ראה |
|
|
|
|
|
|
||
|
||||
|
הידע שלי בנושא זעום עד לא קיים, לכן אני מתנצל מראש על טיפשיות השאלה. (אני יתייחס בשאלה שלי לאופטימיזציה של פונקציה לינארית של 2 משתנים כי יותר קל לדמיין את זה, אבל זה נראה לי נכון לכל מספר משתנים שהוא) אם יש לי אוסף של הגבלות לינאריות, החיתוך שלהם אמור להיות מצולע כלשהו, או תחום לא חסום. משהו מעומעם שאני זוכר מאינפי, אומר לי שכל נקודות המקסימום והמינימום של פונקציה לינארית בתוך המצולע חייבות להתקבל על הקודקודים (משהו עם זה שהנגזרת תמיד שונה מ-0). במידה והתחום לא חסום - לא הוכחתי פורמלית, אבל נראה לי שאו שהפונקציה לא חסומה, או ששוב היא מקבלת מינימום/מקסימום על הקודקודים. מן הסתם אני מפספס משהו, ואני מניח שזה קשור לזכרונות הלא ממש מדוייקים שלי משיעורי אינפי. מישהו מוכן להעמיד דברים על דיוקם? |
|
|
|
|
|
|
||
|
||||
|
הכל נכון - רק שמספר הקודקודים של הקומפלקס הוא אקספוננציאלי במספר המשוואות... | |
|
|
|
|
|
||
|
||||
|
אם יש לי n משוואות, אני לא אמור לקבל מצולע עם (עד) n צלעות? האם למצולע עם n צלעות אין בדיוק n קודקודים? אפילו מספר נקודות החיתוך הכולל של n משוואות לינאריות הוא לפי דעתי סדר גודל של n^2. שוב, אני כנראה מחמיץ משהו בסיסי... |
|
|
|
|
|
|
||
|
||||
|
מימד. אתה מדבר על המישור (שני משתנים), שם הכל באמת קל. כשהמימד גדל, כלומר כשיש הרבה משתנים, מספר הקדקודים, ובאופן כללי הפאות, עשוי להיות גדול מאוד גם אם אין הרבה מדי משוואות. דוגמה: את הקוביה ה-n ממדית אפשר להגדיר ע"י 2n אי-שוויונים: 0 <= xi <= 1 אבל יש לה שתיים-בחזקת-n קדקודים.
|
|
|
|
|
|
|
||
|
||||
|
נפל האסימון. זה מה שקורה שמנסים להוכיח טענות באמצעות "נראה עבור n=2, ההוכחה הכללית דומה". תודה רבה על ההבהרה (לך ולעוזי). |
|
|
|
|
|
|
||
|
||||
|
יש לך קישור טוב למשהו שכתוב פשוט ובהיר על כהנמן ומחקר כלשהו שהוא עשה על הרגלי צריכה של סטודנטים? | |
|
|
|
|
|
||
|
||||
|
לא ברור לי למה אתה מניח שדווקא אני אדע דבר כזה. הידע שלי בתורת המשחקים (זו הסיבה?) הוא אפסי, וכולל קורס בסיסי אחד ועוד טיפה, אז אני חושש שאני לא יכול לעזור לך. אם הצדקת את הכינוי (הקבוע) שלך, וזו הייתה הערה ארסית, פספסתי לגמרי את העוקץ, סליחה. |
|
|
|
|
|
|
||
|
||||
|
שום ארסיות,פשוט חיפשתי עליו ופתאום הופעת עם תורת המשחקים... בינתיים מצאתי משהו קטן. |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי שיש הרבה מה להוסיף מעבר להסבר של ילדה, אלא אם כן אתה רוצה יותר פרטים טכניים. כדאי להזכיר שבתכנון לינארי יש תופעה חשובה של "דואליות" - לכל בעייה יש בעייה צמודה, ולפעמים הרבה יותר קל לפתור אותה. יש דוגמאות נאות בכל מיני מצבים מעשיים. הפניות למקומות שמסבירים יש בלי סוף. הנה ספר על הרשת: הספר הלא אלקטרוני שאני מכיר הוא זה של סחרייבר (Schrijver) ועוד כמה אנשים. |
|
|
|
|
|
|
||
|
||||
|
שמתי לב שלא זכרתי לגמרי נכון: המחלקה המשמעותית לגבי חישובים קוונטיים היא BQP: השפות שניתן למצוא בוודאות גדולה. בינתיים אין שום שפה שלגביה יכולים להגיד בוודאות שהיא ב־BQP אך לא ב־BPP (כלומר: שאין דרך לזהות אותה בוודאות גדולה ע"י מחשב רגיל). מה שכן, יש כמה בעיות חשובות שלהן ידוע אלגוריתם יעיל לפתרון ע"י מחשב קוואנטי. לדוגמה: פירוק לגורמים (שעל הקושי שלה מבוססת, בין השאר, הצפנת RSA) ולוגריתם דיסקרטי (אלוגריתם דיפי-הלמן להחלפת מפתחות, חתימת אלגמאל ותקן DSA). האלגוריתמים הללו נמצאים בשימוש נרחב היום. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |