קיום פיתרון

[the new L]

קיום פיתרון

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

 

[vinney]

זה קצת בעיה

כי הוכחה שקיים פתרון זה הצגת פתרון, לפחות ככה אני חושב שזה מוגדר

יש מלא בעיות במתמטיקה ומדעי המחשב שלא ידוע אם יש להן פתרון (כמו P=NP למשל), אבל יש לא מעט בעיות שידוע שאינן כריעות (ואז אין אלגוריתם כלל), או ידוע שכריעות (ואז ישנו אלגוריתם כלשהו שפותר אותן), אבל לא ידוע אלגוריתם הפותר אותם בסיבוכיות נדרשת (כמו בעיות NPC).

 

[כרובית הפלא]

לא מדוייק../images/Emo70.gif../images/Emo70.gif

ל-NP=P, ידוע שיש פיתרון! רק לא ידוע מהו... כלומר ידוע שיש פיתרון והוא אחד מהפיתרונות הבאים:

NP שווה ל-P

NP שונה מ-P רק לא ידוע מי מהם...

 

[ron369]

כן, ידועות

בערך. זה תלוי בהגדרה של אלגוריתם. אם אתה מגדיר אלגוריתם ע"י תיאור בעזרת פונקציה ניתנת לחישוב, ומנסה להראות שאת התוצאה אי אפשר לחשב עם כל אלגוריתם ידוע, יש פה מעין סתירה, נראה לי. כמו להגיד שאתה מוכיח את טענה א' בעזרת ב', וטענה ב' נכונה בגלל טענה א'. מעין סתירה מעגלית. אם אתה מאפשר להגדיר אלגוריתם במילים, כמו שמאד נחמד לעשות, מה עם: תהי P(x) התכנית שמחזירה 1 לכל קלט אם השערת גולדבאך נכונה, ו-0 אם השערת גולדבאך אינה נכונה. בהנתן שהטענה הזו או נכונה או לא נכונה (אני מפחד להגיד "חייבת להיות או נכונה או לא נכונה), נראה לי שזה טריוויאלי.

 

[vinney]

טוב, זה לא חוכמה ../images/Emo6.gif

 

[ron369]

זה טריק מלוכלך, אבל הוא מדגים משהו

יש דוגמאות הרבה יותר אלגנטיות, למשל, לא ידוע האם יש אינסוף מספרים ראשוניים תאומים. מצאתי באינטרנט את זה: f(x) = 1 אם יש לפחות x מספרים ראשוניים תאומים.

 

[ron369]

ואחרת 0, כמובן ../images/Emo6.gif

 

[vinney]

כן, אבל זה לא מה שלירן שאל

לירן שאל אם יש בעיה שידוע שיש פתרון, אבל לא ידוע מהו. לבעיות שאתה נתת, גם השארת גולדבאך, וגם ראשוניים תואמים - |הגדש|לא ידוע אם יש פתרון.

 

[ron369]

וזה לא מה שעשו?

נתנו בעיה, שידוע שיש לה פתרון (או שיש אינסוף מספרים ראשוניים תאומים, או שאין. בכל מקרה, יש פתרון, יש תשובה), רק לא ידוע מה אותו פתרון (יש כמה אפשרויות, שאחת מהן בהכרח נכונה. רק לא ידוע מי מהן). זהו.

 

[ron369]

הערה

אתה מתבלבל בין "הפתרון הוא XYZ", לבין "יש פתרון, רק לא ידוע מה הוא". מה שעשיתי (ואחרים) מנצל את ההבדל הזה.

 

[vinney]

כמו שאמרתי, לא נראה לי שלזה הוא

אתה רוצה אלגוריתם שפותר אותה? תעבור על כל המספרים האפשריים - קיבלת פתרון. הרי לך אלגוריתם.

 

[ron369]

תרשום את האלגוריתם

אז אולי תבין את הסתירה. למשל, עבור f(100000). נניח שאנחנו עכשיו במספר 2^1000000. אולי אם ננסה עוד מספר אחד, נגיע למספר הראשוני עם תאום ה100000? ואולי עוד טריליארד מספרים? ואולי לעולם לא? איך נדע מתי נפסיק ונדפיס 0?

 

[vinney]

רון

כל בעיה שלא ידוע אם יש לה פתרון אפשר לתרגם לבעיה "האם לבעיה יש פתרון X?" והתשובה תהיה כן או לא, אבל לא נדע מהי כי לא ידוע אם בכלל יש פתרון לבעיה. אני מאמין, ובוא נחכה שלירן יבוא ויגיד לנו, שלא לזה הוא התכוון. אז אני יודע שאתה יודע להתחכם, אבל בוא נחכה למי ששאל את השאלה שיבהיר למה הוא מתכוון.

 

[the new L]

רון דווקא צודק

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

 

[ron369]

אני מאושר ../images/Emo13.gif [נצל"ש מועדי ב']

אני צריך לעשות מועדי שיפור ציון של סוף התואר בקרוב. יש לי שתי פרמוטציות אפשריות. מה נשמע פחות גרוע? - אלגברה לינארית I, ואז הנדסת תכנה: תכנות ועיצוב מונחה עצמים, ואז חשבון אינפיניטיסימלי I - חשבון אינפיניטיסימלי I, אלגברה לינארית I, הנדסת תכנה: תכנות ועיצוב מונחה עצמים - לוותר על הכל. בהנחה שבאינפי ובלינארית שכחתי הכל, ושבהנדסת תכנה לא ידעתי כלום מראש.

 

[vinney]

לוותר על הכל

אם שכחת הכל, אתה צריך לחזור על הרבה מאוד חומר ולעשות הרבה מאוד תרגולים,ולו רק כדי לחזור לרמה שלך שהיית בסוף הקורסים, שלא לדבר על לשפר. על איזה ציון מדובר?

 

[ron369]

ציון רע ../images/Emo8.gif

60 באינפי, 68 בלינארית, 78 בעדה ועשיתי את שני הראשונים לפני בערך שנתיים. התקווה שלי היא שלמרות שאני לא זוכר הרבה, אולי אחרי שאני אחזור על החומר, אני אזכר מהר (יותר מהר מללמוד מההתחלה).

 

[vinney]

צרות של עשירים...

יש לך הרבה זמן אני רואה... מה הממוצע שלך? אם תשפר כל אחד ב10 נקודות, זה יעלה לך את הנקדוה ב1.67 (לכל היותר). האם אתה בטוח שזה שווה את הזמן שתשקיע בזה?

 

[ron369]

למה צרות של עשירים?

זה בהחלט שווה את הזמן. לדעתי הייתי משפר גם אם כולם היו 80, כי אין לי ברירה. ולא, אין לי הרבה זמן, רק הרבה עבודה (והרבה רצון לדחות אותה ככל האפשר, אני פשוט לא יכול).

 

[vinney]

אם היה לי את הזמן גם אני הייתי

משפר חצי מהתואר