שאלה קטנה ברדוקציות פולינומיאליות.

[gil levi]

שאלה קטנה ברדוקציות פולינומיאליות.

השאלה בתמונה. האם הטיעון הבא נכון (וגם הנימוק שלו), ואם לא- מדוע? "הבעיה בNP: הניחוש יהיה המקדם של x^n ולבדוק אם הוא שונה מאפס לוקח זמן פולינומיאלי". תודה מראש.

 

[vinney]

נשמע הגיוני...

אבל אני לא מצליח לחשוב על רדוקציה...

 

[ron369]

במקרה אני מכיר משהו דומה ../images/Emo13.gif

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

 

[gil levi]

תגובה לשניכם.

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

 

[ron369]

ודרך בדיקת המקדם נעשית... כיצד?

 

[gil levi]

../images/Emo4.gif לא ברור.

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

 

[ron369]

אתה, אבל, מניח שניתן "לגשת" למספר

החמישי במספר, למשל, בפולינום התוצאה, ו"לדגום" את ערכו, נכון? (אגב, האורך של מספר המתקבל מהכפלת מספרים פולינומיאליים באורכם הוא, בהכרח, פולינומיאלי באורכו בעצמו. כנ"ל לגבי גודל פולינומיאלי) אנסה להראות שקיימת אפשרות שבה אי אפשר לעשות זאת (לכל n), מבחינה אינטואיטיבית. תחשוב על הבעיה בצורה כזו. נתונות n פסוקיות (clauses) של ai+bi*x^ni. ברור, שלכל גורם בתוצאה, קיים (לפחות אחד) צירוף של ai-ים, ו- bi-ים, כך שמופיע לכל היותר גורם אחד מכל פסוקית. כלומר, כל גורם p_i * x^i מורכב בעצם ממכפלה של b-ים ו-a-ים, כך שסכום החזקות ב-x-ים הקשורים ל-b הוא i. נכון? ומכיוון שיש n פסוקיות, יכול להיות שכל צירוף של שונה של בחירת a-ים או b-ים ייצור חזקה שונה, ולכן גודל התוצאה יהיה אקספוננציאלי (בערך) ב-n. האם הדרך נכונה? מצטער אם ההודעה מעט מבולגנת, אבל עכשיו 3 וחצי בלילה, ובנוסף, אני לא פוסל את האפשרות שעשיתי זאת לחינם - אולי התבלבלתי.

 

[gil levi]

הבנתי פחות או יותר,

אבל לא לכך התכוונתי. התכוונתי שאם יש פתרון לבעיה, אפשר לבדוק שהוא נכון בזמן פולינומיאלי. ה"עדות" שהמקדם של X^n שונה מאפס תהיה פשוט המקדם של X^n ואם מישהו יוכל לתת לי את המקדם הזה אז אני אוכל לבדוק בזמן פולינומיאלי אם הוא שונה מאפס. פשוט נותנים לי את המקדם, נסמן אותו ב K, ואני צריך לבדוק אם K=!0. עד עכשיו חשבתי השוואה כזאת לוקחת זמן קבוע, אז אני לא מבין מדוע הורידו לי נקודות.

 

[shirbi]

לא מבין את הפתרון שלך.

איך בדיוק אתה מבצע את הבדיקה האם המקדם שונה מאפס?

 

[gil levi]

בודק סיבית סיבית.

נניח המקדם הזה הוא K (פשוט מספר טבעי K) אז אני בודק סיבית סיבית במספר אם היא 0. אם כולן אפס אז K=0. בעצם יש כאן שאלה שונה. בהינתן מספר טבעי K, כמה זמן לוקח לבדוק אם K!=0. הטענה שלי היא שאם נבדוק סיבית סיבית אז זה ייקח זמן פולינומיאלי. האם זה נכון?

 

[ron369]

זמן פולינומיאלי, אם מפרטים קצת,

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

 

[gil levi]

אהההה. הבנתי. תודה רבה.

 

[shirbi]

רגע, אז יש פתרון?

אז איך מוכיחים שהבעיה הזאת נמצאת ב NP?

 

[ron369]

מהמרים על צירוף של a-ים וb-ים כלשהם

 

[gil levi]

ו ni -ים, כדאי שנוכל לבדוק

שהa-ים והb-ים באמת שם, נדמה לי. בכל אופן, כאן יש לינק לפתרון של הבחינה. זו שאלה ראשונה.

 

[ron369]

כמובן, לכך התכוונתי, אני חושב ../images/Emo13.gif