בתשובה להאייל האלמוני, 19/01/08 18:10
468607
לקלט מותר לייצג מה שאתה רוצה. כל עוד "טבלת האמת האינסופית" מוגדרת היטב, זה חוקי. אני לא יכול להגיד שאני מבין גדול (או קטן) במשוואות דיופנטיות אבל יש מספר נקודות עדינות שיש לתת עליהן את הדעת:

1. "בהינתן הפתרונות ניתן לבדוק זאת" - אם הקלט הוא A ואתה מרשה פתרונות אקספוננציאלים ב- A אתה בבעיה. בהגדרה של NP אורך ההוכחה חייב להיות פולינומי באורך הקלט.

2. אי קיום נוסחה לא אומר שאין אלגוריתם לפתרון הבעיה. אין נוסחה לפונקציה קדומה של (exp(-x^2 ובכל זאת אפשר לחשב ערך של פונקציה קדומה כזו (עם תנאי שפה מסוימים) בכל נקודה בכל דיוק.

3. גם אם אי אפשר להוכיח שאין לבעיה פתרון, זה לא אומר שאי אפשר להראות שאין לה פתרון בתחום מוגבל (למעשה בטוח שאפשר, השאלה בכמה זמן).

עדיין לא הבנתי מה הדוגמא שלך אמורה להראות, בעיה ב- NP שאינה ב- P? אם כן, שים לב שדי קשה להוכיח שבעיה (כריעה) כלשהי אינה ב- P.
468609
גם אתה וגם גדי מצאתם חורים בטענה, שנבעו בין היתר מהסתמכות על מקור מפוקפק בשם ויקיפדיה העברית, שם נכתב "לחלק מהמשוואות הדיופנטיות, לא קיימת דרך ישירה למציאת הפתרונות, חוץ מבדיקת כל האפשרויות...", אני מניח שמשפט זה לא הוכח כראוי ? אם אכן נדרש מעבר על כל הפתרונות, בלי קשר לקושי לבדוק פתרון יחיד, כמות הפתרונות מוציאה את הבעיה מתחום הפולינומי.
דווקא 1 לא נראה לי כמכשול, כי אם אני מרשה מספרים עד e^A, מספר הספרות יגיע עד ~ln(e^A)~A ולכן הכפלה וחיבור של מספר כזה של סיביות יהיה פולינומי בA.

דווקא להראות שהבעיה אינה בP נדמה לי שהצלחתי (אם קיים אלגוריתם חיפוש פתרונות ביעילות f(n), אני מגדיל את הטווח לF(n) כשf(F(n)=e^A)), הבעיה שאז וידוא הפתרון (כפי שציין גדי) אינו פולינומי.
468610
אני חושב שהם מתכוונים שלא ידועה דרך אחרת למציאת הפתרונות ולא שלא יכולה להתקיים כזו.

לגבי האורך - אתה צריך להיות פולינומי באורך הקלט ולא בערכו. אפשר להגדיל מלאכותית את אורך הקלט אבל אז גם לאלגוריתם מותר לרוץ בזמן יותר ארוך (ואז הבעיה יכולה אפילו להפוך להיות ב- P).

לגבי הטענה האחרונה שלך, מי אמר שכדי לבדוק אם יש פתרון בתחום (סופי) מסוים צריך "אלגוריתם חיפוש פתרונות"? יכול להיות שיש שיטה הרבה יותר פשוטה שאף אחד עוד לא גילה. בכל מקרה ברגע שאתה מפסיק להיות פולינומי באורך הקלט כבר לא ברור אם הבעיה ב- NP.
468612
הקלט הוא A, המרחב בו מחפשים פתרונות גדול יותר, אבל זה לא קשור לקלט אם הבנתי נכון. וידוא הפתרון הוא אכן פולינומי בA, כי המספר המקסימלי שתאלץ לבדוק הוא e^A, עליו תאלץ לבצע פעולות כפל וחיבור. מספר הסיביות במספר פרופורציונלי לA ולכן פעולות כמו כפל וחיבור יהיו פולינומיות בA.

אם יש לך אלגוריתם שמוצא פתרון (אם יש) עבור תחום קטן מn בלי הגבלה על גודלו של n ובזמן שלא תלוי בn, אז אתה יכול להשאיף את n לאינסוף ולדעת האם יש או אין פתרון למשוואה, בסתירה למה שבר הוכח.
468618
אני אדם פשוט, וגם ריבוי האלמונים לא עוזר לי - בהנחה שאתה מי שהתחיל את הדיון הזה, תוכל לכתוב הודעה מסודרת שבה אתה מסביר, מההתחלה ועד הסוף, מה בדיוק אתה מנסה להוכיח כאן?
468622
ההודעות האחרונות היו סתם טרחנות בנוגע לנקודת הכשל. לא הצלחתי להוכיח דבר, לכן אחסוך את זמנך.
468623
טרחנות זו בטח לא, והגישה שלך דווקא סיקרנה אותי.
468746
הרעיון היה לנצל את העובדה שמספר בן A סיביות נמצא בטווח מספרים בן שתים בחזקת A סיביות. כלומר אם תהיה לי שאלה שאפשר לוודא את הנכונות שלה בזמן פולינומי(NP), אבל אין דרך למצא את הפתרון שלה (כמובן הכל בשלמים, או לכל הפחות בקבוצה לא צפופה, אם כי גם כאן בטח יש הסתייגויות שאני לא מכיר), אני אוכל באמצעות הקלט להגדיר טווח מספרים גדול מספיק כדי שזמן מציאת הפתרון יהיה אקספוננציאלי(לא בP). הידע שלי במתמטיקה הוא סימלי לכל היותר, לכן לא היו לי יותר מדי בעיות לבחור מהן. עבור משוואות דיופונטיות ידעתי שיש משוואות שלא ידוע האם יש להן פתרון. אם היתה הוכחה שחיפוש הפתרון באמת מצריך מעבר כל כל המספרים בטווח, יכול להיות שההוכחה היתה עובדת. לרגע גם טעיתי לחשוב שאם החיפוש (של הפתרון) הוא ביעילות כל שהיא (שכמובן חייבת להיות תלויה בn, המספר המקסימלי בטווח שמחפשים בו), אני אוכל לבנות פונקציה שתרחיב את הטווח כך שזמן החיפוש עדיין יהיה אקספוננציאלי. אני באמת יכול לעשות את זה, אבל אז הפתרון גדל כל כך שאני כבר לא יכול לוודא את נכונותו בזמן פולינומי בA.
468748
הגישה שלך בכלל לא מופרכת. בפרט, היא פחות או יותר הבסיס לקריפטוגרפיה המודרנית; למשל, בעיית הפירוק לגורמים, שהיא ‏1 מה שעומד מאחורי RSA סובלת מקושי שכזה. הרעיון הוא שאפשר לייצג די בקלות מספרים גדולים, בני מאות ספרות (כי צריך רק מאות ביטים בשביל זה), וגם די קל לעבוד איתם - חיבור וכפל, למשל, הם פולינומיים במספר הביטים, וגם העלאה בחזקה מודולו משהו היא פולינומית במספר הביטים אם משתמשים באלגוריתם פשוט אך לא נאיבי; אבל פירוק לגורמים נאיבי דורש בדיקה של כל המספרים הקטנים ממה שרוצים לפרק ‏2 וכאלו יש במספר שהוא אקספוננציאלי במספר הספרות. כמובן, כבר ידועים אלגוריתמיים יותר מתוחכמים לפירוק לגורמים, אבל גם הם עדיין אקספוננציאליים, אם אין לך מחשב קוואנטי פועל בהישג יד.

------------
1 לא בדיוק; אם פותרים פירוק לגורמים הלך על RSA, אבל אולי אפשר לחסל את RSA בלי לפתור את בעיית הפירוק לגורמים.

2 טוב, "עד השורש" הידוע.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים