בתשובה לגדי אלכסנדרוביץ', 13/05/06 9:07
P=NP כמובן 384923
easy • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 10:42
כמובן.

כפי שאתה ודאי יודע, פירוק לגורמים הוא לא בעיה שלמה בNP, כלומר יתכן שיש לבעיה פתרון פולינומיאלי גם אם P≠NP.
אני כבר לא זוכר מה למדתי בשיטות הצפנה, אבל היה משהו על היכולת לבנות פולינום מהפתרונות שלו לעומת חוסר היכולת לפתור פולינום (מדרגה מספיק גבוהה).
P=NP כמובן 384927
גדי אלכסנדרוביץ' • בתשובה לeasy שבת, 13/5/2006, 11:26
על פניו, מה שאתה אומר על פולינום נשמע כמו NP: אם קל לבנות פולינום מהפתרונות שלו, הרי שקל גם לוודא שהצלחנו לנחש את הפתרונות שלו (פשוט נבנה את הפולינום על פי הפתרונות ונשווה לפולינום שאנחנו מנסים לפתור). אולי הבעיה נובעת מזה שעלולים להיות המון פתרונות ביחס למשאבים שנדרשים לייצג את הפולינום, אבל אני לא בטוח אם לזה התכוונת.
P=NP כמובן 384937
easy • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 11:49
אני כבר באמת לא זוכר, אבל אם מציאת פתרונות של פולינומים היתה בעיה ב-NP, אז גלואה כבר הוכיח ש P≠NP.
P=NP כמובן 384949
האלמוני ממנג • בתשובה לeasy שבת, 13/5/2006, 12:32
האם משנה דרך מציאת הפתרונות (אם לשים את הקלפים על השולחן - האם פתרון נומרי מספיק "טוב" להגדרה זו)? ובכל מקרה - מהי היעילות של שיטת ניוטון-רפסון (משולבת עם "ציד אריות", במידת הצורך)?
P=NP כמובן 384952
easy • בתשובה להאלמוני ממנג שבת, 13/5/2006, 12:44
אני לא יודע. (בכל מקרה יש לך את מגבלת הדיוק של המודל החישובי שלך, כך שכל ערך מספיק קרוב לפתרון הוא פתרון נומרי.)
P=NP כמובן 384953
גדי אלכסנדרוביץ' • בתשובה לeasy שבת, 13/5/2006, 12:47
כדאי להיזהר עם מה שמייחסים לגלואה. גלואה הוכיח שלא ניתן לפתור *באמצעות רדיקלים* את *המשוואה הכללית* ממעלה חמישית ומעלה (וגם הצביע על דרך יפהפיה לדעת עבור כל משוואה האם היא פתירה באמצעות רדיקלים או לא). זה לא אומר שלא ניתן לפתור את המשוואה - זה תלוי בצורה שבה אתה מגדיר "פתרון". לעצם העניין, אם אתה מסוגל לייצג את השורשים בדרך כלשהי, אז גם אפשר לפתור את המשוואה ולקבל את השורשים באותה דרך ייצוג (עוברים על כל מרחב הפתרונות האפשריים בצורה סדרתית ועבור כל אוסף פתרונות בודקים אם הפולינום שנגזר ממנו הוא הפולינום שאת הפתרונות שלו מחפשים).

כדאי גם לזכור שכשאנחנו חושבים על פולינומים אנחנו חושבים על פונקציות במספרים ממשיים, אבל אין ייצוג דיגיטלי למספרים ממשיים אלא רק לקירובים (רציונליים) שלהם.
P=NP כמובן 384957
easy • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 12:59
פתרונות של פולינומים במקדמים שלמים הם לא כל הממשיים אלא רק המספרים האלגברים, שהם קבוצה בת מניה וניתנת ליצוג מדוייק במחשב (אבל בד''כ מעדיפים להשתמש בקרוב רציונלי).
P=NP כמובן 384958
גדי אלכסנדרוביץ' • בתשובה לeasy שבת, 13/5/2006, 13:07
צודק, אבל זה רק משחק לטובתי: זו קבוצה בת מנייה ולכן אפשר לסרוק אותה באופן סדרתי (לפחות בתיאוריה).
P=NP כמובן 384960
easy • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 13:19
ברור, אבל אתה יכול להראות איך אתה מבצע סריקה כזאת במסגרת NP?
P=NP כמובן 384969
גדי אלכסנדרוביץ' • בתשובה לeasy שבת, 13/5/2006, 14:00
אם הפולינום מדרגה n, אני מנחש n מספרים אלגבריים ובודק אם הם יוצרים את הפולינום.

אם אתה רוצה משהו דטרמיניסטי, זה הופך לשאלה המעניינת של איך סורקים את הכל בצורה סדרתית, וזו שאלה טכנית שבשביל לענות עליה צריך לדעת מה הייצוג שלך למספרים אלגבריים. בצורה הכי פשוטה אפשר לעבור על כל הרצפים האפשריים של 0 ו-‏1, ועבור כל רצף ראשית לבדוק האם הוא מייצג מספר אלגברי חוקי, ואם כן אז אפשר לקחת אותו.
P=NP כמובן 385010
אלון עמית • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 21:11
"בצורה הכי פשוטה אפשר לעבור על כל הרצפים האפשריים של 0 ו-‏1" - אתה בוודאי מתלוצץ.
P=NP כמובן 385021
האייל האלמוני • בתשובה לאלון עמית שבת, 13/5/2006, 21:45
הוא בטוח מתלוצץ.
P=NP כמובן 385028
גדי אלכסנדרוביץ' • בתשובה לאלון עמית שבת, 13/5/2006, 22:31
אה... לא.
P=NP כמובן 385031
אלון עמית • בתשובה לגדי אלכסנדרוביץ' שבת, 13/5/2006, 22:34
אני כנראה לא מבין אותך. רצפים סופיים? אינסופיים?
P=NP כמובן 385032
גדי אלכסנדרוביץ' • בתשובה לאלון עמית שבת, 13/5/2006, 22:37
סופיים. אני מניח (מן הסתם) שייצוג במחשב של מספר אלגברי הוא סופי.
P=NP כמובן 385052
אלון עמית • בתשובה לגדי אלכסנדרוביץ' יום א', 14/5/2006, 0:22
עכשיו אני מבין למה התכוונת. אתה צודק בעניין המנייה, אבל נדמה לי שאתה מפספס את העיקר. אתה מטאטא הצידה את שאלת הייצוג, אבל היא לב העניין: איך אתה מייצג מספרים אלגבריים ע"י מחרוזת של ביטים, והאם הייצוג מספיק יעיל כדי לבדוק שמחרוזת כזו מייצגת שורש של פולינום נתון בזמן פולינומיאלי באורך הקלט? ("אורך הקלט" הוא גודל הייצוג הבינארי, נניח, של מקדמי הפולינום). כל עוד לא הסברת את הפרטים הללו, לא ממש התקדמת בשאלה האם הבעייה היא ב-NP או לא.

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

ייצוג אחר יכול, למשל, לבנות כל מספר אלגברי ממספרים רציונליים תוך שימוש בארסנל מצומצם ככל האפשר של פעולות. זה כבר יותר דומה למובן הקלאסי של "פתרון", ואם נשים בארסנל את ארבע פעולות החשבון, שורשים ו"אולטרא-שורשים" אכן נוכל לייצג כל מספר אלגברי. האם בייצוג הזה יש בכלל חסם פולינומי על אורך הפתרון כפונקציה של המקדמים? זה כלל לא ברור.
P=NP כמובן 385056
גדי אלכסנדרוביץ' • בתשובה לאלון עמית יום א', 14/5/2006, 0:40
אתה צודק, אבל שים לב שאני ו-easy גלשנו מתחומי הסיבוכיות לחישוביות כשהוא עירב את גלואה, ועל זה דיברתי.

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

אבל באמת, בשביל להגיד עוד על העניין הזה אני צריך לשמוע תיאור מפורט של השיטה. בינתיים אני מסתפק במה שאמרו גדולים ממני.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות