בתשובה להאייל האלמוני, 19/01/08 15:36
 |
|
 |
||
|
||||
 |
תודה לך ולגדי. הסבה לפונקציה בינארית היא טריוויאלית (האם קיימת דיסקית אדומה ?), לגבי היות הקלט סמוי, מותר לי להשתמש בקלט כדי למפות לתחום בשדה המספרים ? למשל בהינתן קלט A, האם קיים פתרון למשוואה דיופונטית מסויימת* בטווח המספרים עד e^A? בהינתן הפתרונות ניתן לבדוק זאת בזמן סביר (כלומר הבעיה בNP) אבל הוכח שאין נוסחה למציאת הפתרון למשוואה (וגם לא ניתן להוכיח שאין לה פתרון). גם אם קיים אלגוריתם למציאת הפתרון שמאפשר לעבור רק על שבריר מהמספרים, ניתן להגדיל את התחום כך שמספר המספרים עליהם יש לעבור יגדל מהר מספיק כדי שלא יהיה פתרון פולינומי. נ.ב. כשאני חורג לתחום הטרחנות הכפייתית אנא הודיעו לי ואני אעבור לדיון המתאים :) *אחת שעונה להגדרות של העדר יכולת למצא פתרון בצורה ישירה. |
 |
 |
 |
|
|
|
||
|
||||
|
צריך להיזהר כאן. משוואות דיופנטיות שייכות ל-RE; כלומר, אם יש למשוואה פתרון, אפשר יהיה למצא אותו, *תמיד*. הבעיה היא רק עם זיהוי משוואות ללא פתרון. לכן להגיד "אין נוסחה למציאת הפתרון" זה לא מדוייק. אבל פרט לכך, אם אתה רוצה לנסות להוכיח פה משהו, תצטרך לתת הגדרות מדוייקות - מה הקלט, מה הרדוקציה, מה התחום וכו'. ייתכן שיתגלה פתאום שלא קל אפילו לבדוק את הפתרונות (כי הם גדולים מדי) או שההמרה למשוואות לוקחת זמן רב מדי, וכדומה. ואחרי זה, גם תצטרך להוכיח שלא קיים שום אלגוריתם שפותר את הבעיה ביעילות (זה שונה מאוד מ"מספר המספרים עליהם יש לעבור גדול" - אולי יש אלגוריתם שלא צריך לעבור על כל המספרים? צריך להוכיח שלא יכול להתקיים כזה). |
|
|
|
|
|
|
||
|
||||
|
לקלט מותר לייצג מה שאתה רוצה. כל עוד "טבלת האמת האינסופית" מוגדרת היטב, זה חוקי. אני לא יכול להגיד שאני מבין גדול (או קטן) במשוואות דיופנטיות אבל יש מספר נקודות עדינות שיש לתת עליהן את הדעת: 1. "בהינתן הפתרונות ניתן לבדוק זאת" - אם הקלט הוא A ואתה מרשה פתרונות אקספוננציאלים ב- A אתה בבעיה. בהגדרה של NP אורך ההוכחה חייב להיות פולינומי באורך הקלט. 2. אי קיום נוסחה לא אומר שאין אלגוריתם לפתרון הבעיה. אין נוסחה לפונקציה קדומה של (exp(-x^2 ובכל זאת אפשר לחשב ערך של פונקציה קדומה כזו (עם תנאי שפה מסוימים) בכל נקודה בכל דיוק. 3. גם אם אי אפשר להוכיח שאין לבעיה פתרון, זה לא אומר שאי אפשר להראות שאין לה פתרון בתחום מוגבל (למעשה בטוח שאפשר, השאלה בכמה זמן). עדיין לא הבנתי מה הדוגמא שלך אמורה להראות, בעיה ב- NP שאינה ב- P? אם כן, שים לב שדי קשה להוכיח שבעיה (כריעה) כלשהי אינה ב- P. |
|
|
|
|
|
|
||
|
||||
|
גם אתה וגם גדי מצאתם חורים בטענה, שנבעו בין היתר מהסתמכות על מקור מפוקפק בשם ויקיפדיה העברית, שם נכתב "לחלק מהמשוואות הדיופנטיות, לא קיימת דרך ישירה למציאת הפתרונות, חוץ מבדיקת כל האפשרויות...", אני מניח שמשפט זה לא הוכח כראוי ? אם אכן נדרש מעבר על כל הפתרונות, בלי קשר לקושי לבדוק פתרון יחיד, כמות הפתרונות מוציאה את הבעיה מתחום הפולינומי. דווקא 1 לא נראה לי כמכשול, כי אם אני מרשה מספרים עד e^A, מספר הספרות יגיע עד ~ln(e^A)~A ולכן הכפלה וחיבור של מספר כזה של סיביות יהיה פולינומי בA. דווקא להראות שהבעיה אינה בP נדמה לי שהצלחתי (אם קיים אלגוריתם חיפוש פתרונות ביעילות f(n), אני מגדיל את הטווח לF(n) כשf(F(n)=e^A)), הבעיה שאז וידוא הפתרון (כפי שציין גדי) אינו פולינומי. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שהם מתכוונים שלא ידועה דרך אחרת למציאת הפתרונות ולא שלא יכולה להתקיים כזו. לגבי האורך - אתה צריך להיות פולינומי באורך הקלט ולא בערכו. אפשר להגדיל מלאכותית את אורך הקלט אבל אז גם לאלגוריתם מותר לרוץ בזמן יותר ארוך (ואז הבעיה יכולה אפילו להפוך להיות ב- P). לגבי הטענה האחרונה שלך, מי אמר שכדי לבדוק אם יש פתרון בתחום (סופי) מסוים צריך "אלגוריתם חיפוש פתרונות"? יכול להיות שיש שיטה הרבה יותר פשוטה שאף אחד עוד לא גילה. בכל מקרה ברגע שאתה מפסיק להיות פולינומי באורך הקלט כבר לא ברור אם הבעיה ב- NP. |
|
|
|
|
|
|
||
|
||||
|
הקלט הוא A, המרחב בו מחפשים פתרונות גדול יותר, אבל זה לא קשור לקלט אם הבנתי נכון. וידוא הפתרון הוא אכן פולינומי בA, כי המספר המקסימלי שתאלץ לבדוק הוא e^A, עליו תאלץ לבצע פעולות כפל וחיבור. מספר הסיביות במספר פרופורציונלי לA ולכן פעולות כמו כפל וחיבור יהיו פולינומיות בA. אם יש לך אלגוריתם שמוצא פתרון (אם יש) עבור תחום קטן מn בלי הגבלה על גודלו של n ובזמן שלא תלוי בn, אז אתה יכול להשאיף את n לאינסוף ולדעת האם יש או אין פתרון למשוואה, בסתירה למה שבר הוכח. |
|
|
|
|
|
|
||
|
||||
|
אני אדם פשוט, וגם ריבוי האלמונים לא עוזר לי - בהנחה שאתה מי שהתחיל את הדיון הזה, תוכל לכתוב הודעה מסודרת שבה אתה מסביר, מההתחלה ועד הסוף, מה בדיוק אתה מנסה להוכיח כאן? | |
|
|
|
|
|
||
|
||||
|
ההודעות האחרונות היו סתם טרחנות בנוגע לנקודת הכשל. לא הצלחתי להוכיח דבר, לכן אחסוך את זמנך. | |
|
|
|
|
|
||
|
||||
|
טרחנות זו בטח לא, והגישה שלך דווקא סיקרנה אותי. | |
|
|
|
|
|
||
|
||||
|
הרעיון היה לנצל את העובדה שמספר בן A סיביות נמצא בטווח מספרים בן שתים בחזקת A סיביות. כלומר אם תהיה לי שאלה שאפשר לוודא את הנכונות שלה בזמן פולינומי(NP), אבל אין דרך למצא את הפתרון שלה (כמובן הכל בשלמים, או לכל הפחות בקבוצה לא צפופה, אם כי גם כאן בטח יש הסתייגויות שאני לא מכיר), אני אוכל באמצעות הקלט להגדיר טווח מספרים גדול מספיק כדי שזמן מציאת הפתרון יהיה אקספוננציאלי(לא בP). הידע שלי במתמטיקה הוא סימלי לכל היותר, לכן לא היו לי יותר מדי בעיות לבחור מהן. עבור משוואות דיופונטיות ידעתי שיש משוואות שלא ידוע האם יש להן פתרון. אם היתה הוכחה שחיפוש הפתרון באמת מצריך מעבר כל כל המספרים בטווח, יכול להיות שההוכחה היתה עובדת. לרגע גם טעיתי לחשוב שאם החיפוש (של הפתרון) הוא ביעילות כל שהיא (שכמובן חייבת להיות תלויה בn, המספר המקסימלי בטווח שמחפשים בו), אני אוכל לבנות פונקציה שתרחיב את הטווח כך שזמן החיפוש עדיין יהיה אקספוננציאלי. אני באמת יכול לעשות את זה, אבל אז הפתרון גדל כל כך שאני כבר לא יכול לוודא את נכונותו בזמן פולינומי בA. | |
|
|
|
|
|
||
|
||||
|
הגישה שלך בכלל לא מופרכת. בפרט, היא פחות או יותר הבסיס לקריפטוגרפיה המודרנית; למשל, בעיית הפירוק לגורמים, שהיא 1 מה שעומד מאחורי RSA סובלת מקושי שכזה. הרעיון הוא שאפשר לייצג די בקלות מספרים גדולים, בני מאות ספרות (כי צריך רק מאות ביטים בשביל זה), וגם די קל לעבוד איתם - חיבור וכפל, למשל, הם פולינומיים במספר הביטים, וגם העלאה בחזקה מודולו משהו היא פולינומית במספר הביטים אם משתמשים באלגוריתם פשוט אך לא נאיבי; אבל פירוק לגורמים נאיבי דורש בדיקה של כל המספרים הקטנים ממה שרוצים לפרק 2 וכאלו יש במספר שהוא אקספוננציאלי במספר הספרות. כמובן, כבר ידועים אלגוריתמיים יותר מתוחכמים לפירוק לגורמים, אבל גם הם עדיין אקספוננציאליים, אם אין לך מחשב קוואנטי פועל בהישג יד. ------------ 1 לא בדיוק; אם פותרים פירוק לגורמים הלך על RSA, אבל אולי אפשר לחסל את RSA בלי לפתור את בעיית הפירוק לגורמים. 2 טוב, "עד השורש" הידוע. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |