בתשובה להאייל האלמוני, 19/01/08 20:33
 |
|
 |
||
|
||||
 |
הקלט הוא A, המרחב בו מחפשים פתרונות גדול יותר, אבל זה לא קשור לקלט אם הבנתי נכון. וידוא הפתרון הוא אכן פולינומי בA, כי המספר המקסימלי שתאלץ לבדוק הוא e^A, עליו תאלץ לבצע פעולות כפל וחיבור. מספר הסיביות במספר פרופורציונלי לA ולכן פעולות כמו כפל וחיבור יהיו פולינומיות בA. אם יש לך אלגוריתם שמוצא פתרון (אם יש) עבור תחום קטן מn בלי הגבלה על גודלו של n ובזמן שלא תלוי בn, אז אתה יכול להשאיף את n לאינסוף ולדעת האם יש או אין פתרון למשוואה, בסתירה למה שבר הוכח. |
 |
 |
 |
|
|
|
||
|
||||
|
אני אדם פשוט, וגם ריבוי האלמונים לא עוזר לי - בהנחה שאתה מי שהתחיל את הדיון הזה, תוכל לכתוב הודעה מסודרת שבה אתה מסביר, מההתחלה ועד הסוף, מה בדיוק אתה מנסה להוכיח כאן? | |
|
|
|
|
|
||
|
||||
|
ההודעות האחרונות היו סתם טרחנות בנוגע לנקודת הכשל. לא הצלחתי להוכיח דבר, לכן אחסוך את זמנך. | |
|
|
|
|
|
||
|
||||
|
טרחנות זו בטח לא, והגישה שלך דווקא סיקרנה אותי. | |
|
|
|
|
|
||
|
||||
|
הרעיון היה לנצל את העובדה שמספר בן A סיביות נמצא בטווח מספרים בן שתים בחזקת A סיביות. כלומר אם תהיה לי שאלה שאפשר לוודא את הנכונות שלה בזמן פולינומי(NP), אבל אין דרך למצא את הפתרון שלה (כמובן הכל בשלמים, או לכל הפחות בקבוצה לא צפופה, אם כי גם כאן בטח יש הסתייגויות שאני לא מכיר), אני אוכל באמצעות הקלט להגדיר טווח מספרים גדול מספיק כדי שזמן מציאת הפתרון יהיה אקספוננציאלי(לא בP). הידע שלי במתמטיקה הוא סימלי לכל היותר, לכן לא היו לי יותר מדי בעיות לבחור מהן. עבור משוואות דיופונטיות ידעתי שיש משוואות שלא ידוע האם יש להן פתרון. אם היתה הוכחה שחיפוש הפתרון באמת מצריך מעבר כל כל המספרים בטווח, יכול להיות שההוכחה היתה עובדת. לרגע גם טעיתי לחשוב שאם החיפוש (של הפתרון) הוא ביעילות כל שהיא (שכמובן חייבת להיות תלויה בn, המספר המקסימלי בטווח שמחפשים בו), אני אוכל לבנות פונקציה שתרחיב את הטווח כך שזמן החיפוש עדיין יהיה אקספוננציאלי. אני באמת יכול לעשות את זה, אבל אז הפתרון גדל כל כך שאני כבר לא יכול לוודא את נכונותו בזמן פולינומי בA. | |
|
|
|
|
|
||
|
||||
|
הגישה שלך בכלל לא מופרכת. בפרט, היא פחות או יותר הבסיס לקריפטוגרפיה המודרנית; למשל, בעיית הפירוק לגורמים, שהיא 1 מה שעומד מאחורי RSA סובלת מקושי שכזה. הרעיון הוא שאפשר לייצג די בקלות מספרים גדולים, בני מאות ספרות (כי צריך רק מאות ביטים בשביל זה), וגם די קל לעבוד איתם - חיבור וכפל, למשל, הם פולינומיים במספר הביטים, וגם העלאה בחזקה מודולו משהו היא פולינומית במספר הביטים אם משתמשים באלגוריתם פשוט אך לא נאיבי; אבל פירוק לגורמים נאיבי דורש בדיקה של כל המספרים הקטנים ממה שרוצים לפרק 2 וכאלו יש במספר שהוא אקספוננציאלי במספר הספרות. כמובן, כבר ידועים אלגוריתמיים יותר מתוחכמים לפירוק לגורמים, אבל גם הם עדיין אקספוננציאליים, אם אין לך מחשב קוואנטי פועל בהישג יד. ------------ 1 לא בדיוק; אם פותרים פירוק לגורמים הלך על RSA, אבל אולי אפשר לחסל את RSA בלי לפתור את בעיית הפירוק לגורמים. 2 טוב, "עד השורש" הידוע. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |