בתשובה לאיזי נבו, 23/05/04 15:24
 |
|
 |
||
|
||||
 |
שוב אנחנו חוזרים לבעייה המקורית, תת-מרחב הפתרונות האפשריים הוא כל כך גדול שבדיקה שלהם תקח ימבה זמן ועד שנמצא את התשובה הנכונה כבר אפשר יהייה לצעוד לירח ובחזרה (עד אז יבנו שביל להולכי רגל). |  |
 |
 |
|
|
|
||
|
||||
|
כיום אין שום אלגוריתם למחשב קוונטי שיכול לפתור בעיה שידוע שהיא קשה (NP-Complete לאלו שמכירים את המינוח) וגם אין נימוק ממש טוב למה שיהיה כזה. כל האלגוריתמים הקוונטיים שידועים כיום ושהם יותר טובים מכל אלגוריתם קלאסי שידוע, הם לבעיות שיתכן שיש להן פתרון קל במחשב רגיל, רק שלא ידוע כזה. | |
|
|
|
|
|
||
|
||||
|
עוד לא הוכח כי בעיות NP-complete הן באמת קשות על מחשב קלאסי. גם להן ייתכן פתרון קל במחשב רגיל. | |
|
|
|
|
|
||
|
||||
|
אתה צודק, אבל הסיכוי שיתגלה פתרון פולינומיאלי לבעיות NP-complete הוא נמוך, לדעת רבים, מהסיכוי שרוזנקרנץ וגילדנשטרן חיים. יש משהו מפתיע, שלא לומר מסתורי, בעובדה שגם בחישוב קוונטי וגם בהצפנה ציבורית עוד לא הצליחו1 להתלבש על בעיות NP-complete, והלא יש כל כך הרבה כאלה. 1 ככל הידוע לי. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |