 |
|
 |
||
|
||||
 |
עד כמה מותר לי לשחק עם החוקים שמגדירים בעיה ? למשל איפה הכשל בבעיה הבאה : נתונה סדרה של דיסקיות מסודרות לפי רוחבן בערמה (בדומה למגדל האנוי) כאשר לאחת הדיסקיות עיגול אדום קטן בצד הפונה מעלה. המטרה היא למצא את הדיסקית הסוררת, מה שניתן לראות רק כאשר היא עליונה. אך במקום שלושה מוטות, מצויים בפניך שני סטים של שלושה מוטות, כאשר אתה מחלק את ערמת הדיסקיות לשני חלקים היכן שתרצה, מניח כל חצי על מוט אחר ומכאן כל סט של שלושה מוטות מתנהג כמגדל האנוי נפרד לכל דבר. הפתרון הפשוט הוא לחלק את הערמה באמצע ואז לשחק בסט אחד ולאחר מכן בשני, הסיבוכיות היא ((O(2^(n/2 כמדומני. אך אם ידוע לך באיזו דיסקית מדובר, הרי עצם חלוקה נכונה תפתור את הבעיה מייד. אני מניח שעצם היות הבעיה דו-שלבית (ולכן "מלאכותית" במובן מסויים) תצרום, שכן האפשרות לוודא את נכונות הפתרון היא חד פעמית, אבל האם יש סט של חוקים המגדיר מה מותר ואסור בהגדרת בעיה ? |
 |
 |
 |
|
|
|
||
|
||||
|
מדידת הסיבוכיות היא בד''כ על פי המקרה הגרוע ביותר מבין אלו שהאלגוריתם אמור לפעול עליהם. כלומר, אם אתה יודע תמיד איפה הדיסקית, בוודאי שהסיבוכיות של כל העניין טריוויאלי - וגם הבעיה טריוויאלית. אם לעומת זאת הדיסקית יכולה להיות בכל מקום והאלגוריתם לא יודע איזה, אז לצורך בדיקת המקרה הגרוע ביותר אפשר להניח שיש ''יריב ערמומי'' שרואה את הפתרון שלך, ושם דיסקית במקום שיגרום הכי הרבה ''נזק''. | |
|
|
|
|
|
||
|
||||
|
אז לא מחשיבים את Quicksort כאלגוריתם שפועל ב nlonn יותר? | |
|
|
|
|
|
||
|
||||
|
לא החשיבו אותו כך אף פעם, כשמדברים על המקרה הגרוע. לכן לעתים קרובות מלמדים אותו בד בבד עם ניתוחי סיבוכיות על פי המקרה הממוצע. | |
|
|
|
|
|
||
|
||||
|
רק במקרה הממוצע (או אם משתמשים באלגוריתם ליניארי למציאת חציון כדי למצוא את הפיבוט). | |
|
|
|
|
|
||
|
||||
|
כמובן. הבעיה היא לא בP כי אין לאלגוריתם דטרמיניסטי דרך לפתור אותה בזמן פולינומי (נובע מההוכחה על האנוי), אבל בהינתן הפתרון, וידוא שלו (רק במהלך הראשון) כן נעשה בזמן פולינומי, לכן היא בNP, מה שהיה מפריך את P=NP אם הבעיה היתה תקפה. השאלה שלי היא למה בדיוק הבעיה לא תקפה ? |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח מה הכוונה ב"לא תקפה". על כל פנים, שים לב שיש כמה הבדלים מהותיים בינה לבין בעיות חישוביות "רגילות" - בפרט, זו בעיה של חיפוש, לא של תשובת "כן/לא", אבל בעיקר (וזה ההבדל המהותי) - היא מבוססת על קלט *חלקי*, שיש בו מידע מוסתר - בעצם, מעין "קופסה שחורה" שצריך להתמודד איתו. הכוונה היא שיכולים להיות שני קלטים שנראים זהה למכונה, ובכל זאת "מתנהגים" שונה (על סמך מהי הדיסקית המסומנת). נראה לי שכאן נמצא ההבדל המרכזי. | |
|
|
|
|
|
||
|
||||
|
"בעיה" היא פשוט פונקציה בינארית במשתנה אחד. יש לה קלט שהוא מחרוזת בינארית כלשהי ולכל קלט יש פלט מתאים (במקרה שלנו הפלט יכול להיות "1" או "0"). אפשר לחשוב על זה כטבלת אמת אינסופית שמתאימה ערך לוגי לכל מחרוזת. פתרון של הבעיה הוא פשוט תוכנה (או "מכונת טיורינג") שמחשבת את הפונקציה הזו. אתה בטח רואה שהניסוח שלך לא עונה לדרישה: אתה לא יכול להגדיר את המשחק שתיארת כפונקציה שהקלט שלה מגדיר באופן יחיד את הפלט (כפי שגדי ציין, על אותו קלט התחלתי יכולים להיות הרבה פלטים שונים). בדרך כלל ב"פתרון בעיות" או "חישוב" הגיוני לדרוש לדעת מה הבעיה לפני שמתחילים לפתור אותה אבל לפעמים העולם לא עובד כך. למשל אני עומד בתחנת אוטובוס ולא יודע מתי האוטובוס יגיע (אם בכלל), כמה כדאי לי לחכות לפני שאני מתיאש והולך ברגל? אלגוריתמי אונליין, למשל, מטפלים בסוג כזה של בעיות. אגב, באופן שקול אפשר להגדיר בעיה כתת-קבוצה של קבוצת המחרוזות (תת-הקבוצה המכילה את כל המחרוזות שהפלט עליהן הוא "1"). במקרה זה, תפקיד המכונה שלך לבדוק האם הקלט שייך לתת-הקבוצה או לא. |
|
|
|
|
|
|
||
|
||||
|
תודה לך ולגדי. הסבה לפונקציה בינארית היא טריוויאלית (האם קיימת דיסקית אדומה ?), לגבי היות הקלט סמוי, מותר לי להשתמש בקלט כדי למפות לתחום בשדה המספרים ? למשל בהינתן קלט 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |