 |
|
 |
||
|
||||
 |
אז ככה, כבר שנים שאני מסתובב עם בעיה שלמה ב NP שיש לי בשבילה פתרון לינארי- אפילו לא חזקה של n. שתי בעיות: 1) להראות שהבעיה שלמה ב NP. 2) להראות שהפתרון נכון תמיד. ניסיתי בעצמי רדוקציות ל SAT ולעוד בעיות שלמות אך ללא הועיל(קנס של 80 ש"ח לאוניברסיטה על איחור בהחזרת הספר ששכחתי את שמו ומתאר את הבעיות הנ"ל). כנראה שהבעיה אינה שלמה ב NP או שכוחי דל. את השלב השני נעבור אחרי הצלחות בשלב הראשון. מי שרוצה להתמודד עם הבעיה מוזמן לפנות אליי. אני בשמחה אשתחרר מהעול הזה, לכאן או לכאן. |
 |
 |
 |
|
|
|
||
|
||||
|
כמו שאני מבין את זה, רדוקציה *ל*-SAT מבעיה שיש לה פתרון ליניארי לא תראה שום דבר. מה שאתה צריך להראות הוא שיש רדוקציה *מ*-SAT *ל*בעיה הנ"ל. אז או שאני מבולבל לרגע, או שאתה מבזבז את זמנך לגמרי כבר כמה שנים. | |
|
|
|
|
|
||
|
||||
|
כן, גם אני התעכבתי רגע כשכתבתי את התגובה ושיניתי מ'מ' ל'ל'. בו נתבונן בזה כך: נסמן את הבעיה שלי ב X ואת האלגוריתם שלי ב P. ובתור בעיית NP ניקח את SAT ואלגוריתם שפותר SAT ב S. עכשיו, ברור שקלט ל X ניתן להריץ על P וקלט ל SAT ניתן להריץ על S. אם נהפוך את הקלט של X ל קלט ל SAT הרי שהראנו ש X טובה לפחות כמו SAT. לא מועיל בהרבה. אבל, אם נראה שאת הקלט של SAT ניתן להפוך לקלט ל X אזי נריץ את P עם הקלט המקורי של SAT, נקבל תשובה בזמן לינארי ולמעשה הפכנו את SAT ללינארית. לסיכום: יש לעשות רדוקציה מ SAT ל X על-מנת להראות ש P=NP, בלי סימן שאלה. אנא תקנו אותי אם הצלחתי לבלבל את עצמי שוב. בכל מקרה. הבעיה עדיין פתוחה: האם הבעיה שיש בידי, כולל הפתרון הלינארי טובים? האם X שלי ב NP או לא? והאם P שלי אכן פותר את כל המקרים. SIMPLEX הוא אלגוריתם שנראה טוב אבל יש קלטים שבהם הוא "נופל". האם גם P כזו? זאת ועוד בפתיל התגובות להלן... |
|
|
|
|
|
|
||
|
||||
|
מצטער, אני מאוד לא אוהב לקרוא טקסטים שהם פחות מברורים לגמרי. אם אתה מעוניין בדעתי, אעדיף למסור לך אותה בצורת הסבר מחדש של הנושא, בלי לנסות לפענח - איתך הסליחה - את מה שכתבת. ידוע שכל בעיה ב-NP, ניתן, בזמן פולינומי, להמיר בבעיית SAT. כלומר, אם אתה רוצה לדעת, למשל, אם יש מעגל המילטוני בגרף שעובר דרך כל הקודקודים, אתה יכול, בזמן פולינומי, ליצור פסוק בוליאני שניתן לסיפוק אם ורק אם היה בגרף שהתחלת ממנו את התהליך מעגל כנ"ל. בשלב הזה, אם מישהו יודע לפתור את SAT בזמן פולינומי, אתם יכולים לעבוד ביחד בכדי לפתור בזמן פולינומי את הבעיה המקורית שלך: אתה תיקח את הבעיה שלך, תמיר אותה בבעית SAT, תמסור אותה לבחור שיודע לפתור בעיות SAT, הוא יחזיר לך תשובה, ואתה תחזיר את התשובה שקיבלת ממנו. כל אחד משני השלבים נעשה בזמן פולינומי, ויחד זה עדיין פולינומי. כלומר, יוצא שאם את בעית SAT ניתן לפתור בזמן פולינומי, אז כל בעיה ב-NP ניתנת לפתירה בזמן פולינומי, ע"פ התהליך הנ"ל (אותו לא תיארתי במלואו. אמרתי שידוע שאפשר לבצע המרה כזאת לכל בעיה ב-NP, אבל לא אמרתי איך). חשוב לשים כאן לב שהבעיה שלך עשויה להיות הרבה יותר פשוטה מהבעיה שאתה מוסר לו הלאה. לדוגמה, אתה יכול להתמודד עם הבעיה המאוד פשוטה של "האם המספר שאני עומד מולו כרגע הוא המספר 31, או כל מספר אחר?" במקרה המנוון הזה, אתה יכול לפתור בקלות את הבעיה, ואז להעביר הלאה, לבחור שפותר את SAT, במידה וקיבלת את המספר 31, את הפסוק "א' או ב"', ובמידה וקיבלת מספר אחר, את הפסוק "א' או לא א"'. התשובה שלו לראשון תהיה "כן", ולשני "לא", אבל אתה לא תלמד מכך שום דבר חדש. מה שאתה מחפש להוכיח הוא ש-SAT ניתנת לפתירה בזמן פולינומי. קלאסית, אתה תנסה לעשות את זה על ידי הצגת אלגוריתם שפותר את SAT בזמן פולינומי. דרך אחת לעשות את זה היא להראות שיש בעיה אחרת, שניתן לפתור אותה בזמן פולינומי, ושניתן להמיר *את SAT בבעיה החדשה הזאת בזמן פולינומי*. שים לא - לא את הבעיה החדשה בבעיית SAT, אלא את בעיית SAT בבעיה החדשה. |
|
|
|
|
|
|
||
|
||||
|
אם אתה רוצה לדבר בחידות, בבקשה, אבל אין סיבה שמישהו יתייחס אלייך ברצינות. תספר מה הבעיה ומה הפתרון, וחסל. אגב, חשוב לזכור שהרדוקציה מ-SAT לבעיה שלך צריכה להיות ניתנת לחישוב בזמן פולינומי. רדוקציה לא פולינומית מ-SAT יש לכל דבר שבעולם (כמעט). |
|
|
|
|
|
|
||
|
||||
|
אפשר דוגמא (לרדוקציה לא פולינומית מSAT או מבעיה NP-שלמה אחרת לבעיה פולינומית)? | |
|
|
|
|
|
||
|
||||
|
בטח. למשל, הבעיה של "האם x הוא 1?" כש-x הוא בתחום 0 או 1. הרדוקציה היא כזו: בהינתן פסוק בתחשיב הפסוקים, בדוק (בזמן אקספוננציאלי, בצורה הנאיבית) אם הוא ספיק. אם כן, העתק אותו ל-1. אם לא, העתק אותו ל-0. מה קיבלנו? שפסוק הוא ספיק אם ורק אם הוא מועתק ל-x שעליו האלגוריתם שפותר את הבעיה הפשוטה עונה "כן". |
|
|
|
|
|
|
||
|
||||
|
ועוד דבר, את החלק של רדוקציה מ SAT לבעית סידור ההזמנות לא הצלחתי להראות בכלל. כלומר אין לי שום אלגוריתם שהופך את SAT לבעית סידור ההזמנות. כך שבוודאי שהוא לא פולינומי. יש לכם משהו? |
|
|
|
|
|
|
||
|
||||
|
זו הפעם הראשונה שבה אני שומע אותך אומר משהו על "סידור הזמנות", אז עדיין לא ברור על מה אתה מדבר. בכל אופן, הצעד הראשון לפני שמתקלים את P=NP הוא לבדוק שניתן לבצע רדוקציה פולינומית מ-SAT (או בעיה NP-שלמה אחרת) אל הבעיה שיש לך ביד . אם אין לך משהו כזה, אין לך בעצם כלום (כלומר, יש לך בעיה שאתה יודע או לא יודע לפתור, אבל אין לה קשר ממשי לשאלת P=NP). |
|
|
|
|
|
|
||
|
||||
|
אני כתבתי תאור ארוך של בעיית סידור ההזמנות, חשבתי שתראה את התגובה ההיא לפני זאת ולכן כבר התיחסתי אליה כאל בעיה שאתה מכיר... תיכף אני אתאר אותה שוב. משום מה היא לא עלתה למערכת (תגיד, צריך ללחוץ על "אישור"? :-)) מלבד זאת, אני לא תוקף את P=NP אני רק רוצה לשייך את בעיית סידור ההזמנות למחלקה הנכונה. בשלב ראשון זה מה שאני לא יודע. אח"כ כבר יהיה יותר קל: אם היא שייכת ל P אזי נוכל להניח שהאלגורתם שמסדר הוא נכון תמיד. אם הבעיה שייכת ל NP אזי נצטרך לעבוד קצת יותר קשה ולהראות שיש לפחות קלט אחד שעבורו האלגוריתם רץ בזמן לא סביר. להלן (שוב) תיאור הבעיה: נתון צי רכבים N. לכל רכב בצי יש מספר תכונות המאפיינות אותו: מספר מקומות, סוג הילוכים, רשיון נדרש, צבע וכד'. נתונה רשימת הזמנות R. כל הזמנה מכילה: 1. מאיזו שעה ועד איזו שעה הרכב נדרש. 2. מאפיינים של הרכב הנדרש. הרשימה יכולה להיות ריקה, כלומר כל רכב מתאים. השאלה: האם קיים סידור ל R ב N? או בגרסה המלאה: מהו הסידור של R ב N? כל מי שהיה פעם חבר קיבוץ מכיר את הבעיה. יש לי גם תאור פורמלי יותר של הבעיה, יותר מאוחר אני אעלה אותו. |
|
|
|
|
|
|
||
|
||||
|
בלי לחשוב על הבעיה יותר מדי, היא נראית לי הרחבה של http://en.wikipedia.org/wiki/Knapsack_problem שהיא בעיה NP שלמה. | |
|
|
|
|
|
||
|
||||
|
במבט חטוף, אני לא מצליח להבין אם יש קשר בין שתי הבעיות. אולי, אם כל פריט הוא הזמנה: משקלו הוא השעות וערכו הוא התיקים אליהם הוא יכול להכנס?... לא נשמע טוב, צריך לבדוק. ודווקא הרחבה יכולה ליצור הקלה בתנאים ולהפוך את הבעיה לפשוטה יותר.... | |
|
|
|
|
|
||
|
||||
|
הנה תיאור של רדוקציה מבעיה דמוית-תרמיל לבעית סידור ההזמנות. הבעיה (דמוית התרמיל): נתונות n משקולות, במשקל כולל N, וצריך למצוא תת קבוצה שלהן כך שסכום המשקולות בתת הקבוצה הוא *בדיוק* K. בנוסף אני דורש ש- 2K>N. רדוקציה: בצי הרכבים יש שני רכבים, 1 ו- 2. אורך ה"יממה" הוא K שעות. כל משקולת הופכת להזמנה של רכב למספר שעות השווה לגודל המשקולת, כאשר ההזמנה היא לרכב 1 או לרכב 2. בנוסף, יש הזמנה של 2K-N שעות לרכב 2 בלבד. סכום השעות בכל ההזמנות הוא בדיוק 2K, וכך גם סכום השעות הזמינות. לכן אם יש פתרון, הוא יהיה חייב לקיים שסכום ההזמנות של רכב 1 הוא בדיוק K, כנדרש. עכשיו, כדי לצמצם את "הפער" בין הבעיה דמוית התרמיל שהצגתי לבין בעית התרמיל המקורית ניתן לפעול בשתי דרכים: או למצוא רדוקציה מבעית התרמיל לבעיה דמוית התרמיל, או לפתח את הרדוקציה הזאת כך שתפתור בעיה יותר כללית. הנה כמה מחשבות על הדרך השניה: הדרישה ש- 2K>N היא דרישה טכנית, שלדעתי אפשר להיפטר ממנה. מה שבטוח הוא שבאופן טריביאלי אפשר לשים כל קבוע אחר במקום ה- 2. לגבי העובדה שאנחנו מוצאים פתרון רק אם הסכום הוא בדיוק K - את זה אפשר היה לפתור אילו בבעית ההזמנות היתה איזושהי "עדיפות" (כלומר, כל כותב הזמנה היה כותב באיזה עדיפות הוא רוצה אילו רכבים, והיינו יכולים להכניס garbage collector נוסף - רכב 3 - שהיה אוסף את כל מי שלא קיבל את הזמנתו). זה גם היה מאפשר להכניס פנימה את עניין הערך לעומת גודל המשקולת לדעתי (אם כי לפי זכרוני המעומעם כבר יש רדוקציה לבעיה שבה הערך הוא המשקולת). זאת בקצרה ובלי לחשוב יותר מדי, והתחושה שלי (בדומה ל- easy) היא שעם נעבוד קצת יותר נגיע לרדוקציה. |
|
|
|
|
|
|
||
|
||||
|
שים לב שכחלק מההזמנה צריך לציין מאיזו שעה עד איזו שעה הרכב נדרש. התכונה הזו מקלה מכיוון שהיא מורידה באופן משמעותי את דרגות החופש של הפתרון. | |
|
|
|
|
|
||
|
||||
|
מצד אחד היא מקלה כי היא מצמצמת את החופש אך מצד שני היא מקשה על האלגוריתם למצוא סידור. חופש בהזזת עשות ההזמנה היה מקל על האלגוריתם, ויתכן אפילו שאחד חמדן היה מוצא פתרון טוב. אגב, האלגוריתם הנאיבי שפותר את הבעיה הוא: 1. כל עוד אין התנגשות שבץ את ההזמנה הנוכחית במקום שמתאים לה. 2. אם אין מקום להזמנה הנוכחית, חזור להזמנה הקודמת ומקם אותה במקום אחר שמתאים לה ושהיא עוד לא היתה בו אף פעם. 3. חזור ל 1. נאיבי, אקספוננציאלי אבל עובד. |
|
|
|
|
|
|
||
|
||||
|
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת. | |
|
|
|
|
|
||
|
||||
|
הערה טכנית: אלגוריתם דטרמיניסטי לא "עובד תמיד נכון", הוא או עובד נכון (תמיד), או לא נכון (מספיק שבמקרה אחד). עוד הערה טכנית: את הבעיה לא הסברת "שוב", הסברת אותה לראשונה. אם אתה מתכתב בנושא בכמה פורומים, מן הנימוס שתזכור עם מי דיברת על מה, או לפחות לא תנזוף באף אחד על שכחה. |
|
|
|
|
|
|
||
|
||||
|
הוא הסביר אותה "שוב", בפעם הראשונה "משום מה היא לא עלתה למערכת" תגובה 468939 (אם אתה נוזף באחרים כדאי שתבדוק שאתה לא נוזף בהם בטעות). | |
|
|
|
|
|
||
|
||||
|
לא הבנתי שכשהוא אומר שהוא ''תיכף יתאר אותה שוב'', הוא מתכוון באותה הודעה ממש. חשבתי שהוא מתכוון עוד שעתיים, כשיגיע זמן הפסקת הצהריים. תודה על התיקון, וסליחה לרן. | |
|
|
|
|
|
||
|
||||
|
עוד לא העליתי את התאור הפורמלי של בעיית סידור ההזמנות, פשוט זה בבית ועוד לא היה לי את הפנאי. אם זה ידרבן מישהו מהקוראים להתעסק עם זה, אני אעלה גם את האלגוריתם. שאלה: מה המשתנה, n, שעליו ניתן לומר שהאלגוריתם עובד ב O כלשהו של n? האם זה צי הרכבים N, האם מספר ההזמנות R? ועוד שאלה: האם טווח השעות בבעיה משנה לשייכותה למחלקה זו או אחרת? כלומר, אם הזמן בו ניתן לבקש רכב הוא סופי, למשל 24 שעות. או אם הזמן הוא לאינסוף. |
|
|
|
|
|
|
||
|
||||
|
לרוב נהוג כשעוסקים בהיבטים תיאורטיים כמו P מול NP לדבר על גודל הייצוג של הקלט. לכן לא סופרים כמה רכבים והזמנות יש, אלא האם כמה מקום לוקח לייצג אותם (בדומה לצורה שבה פונקציות על מספרים נמדדות בסיבוכיות שלהם לא ביחס לגודל המספרים, אלא לגודל הייצוג שלהם, שהוא לוגריתמי בגודל המספר כשאנחנו בבסיס ספירה גדול מ-1). | |
|
|
|
|
|
||
|
||||
|
למעשה אתה טוען שזה שקלול של השניים. זה בסדר, אין לי בעיה עם זה. ומה לגבי מהותו של עניין - לאיזו מחלקה הבעיה שייכת? |
|
|
|
|
|
|
||
|
||||
|
הבעיה שאתה מציג היא מסוג בעיית תזמון משאבים בגרף אינטרוולים. הבעיות האלה מעניינות בהקשר של P/NP כיוון ששינוי מאוד קטן בהגדרת הבעיה מעביר אותה מ- P ל- NPC. ספציפית נראה לי שהבעיה שאתה מתאר נמצאת ב- P אבל אני לא יודע להציג לה אלגוריתם ובפרט אני לא רואה אלגוריתם "סטנדרטי" שעובד בזמן ליניארי (אני חושב שצריך זמן ריבועי או משהו כזה). | |
|
|
|
|
|
||
|
||||
|
כמו שאמרו כאן, זו בעייה בסגנון "Interval Graph". אני לא מבין כלום בנושא, אבל אני מכיר מישהו שמבין ואשאל אותו. | |
|
|
|
|
|
||
|
||||
|
זה מאד יעזור, תודה. | |
|
|
|
|
|
||
|
||||
|
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות. (אם הקשר לא ברור - "צבע" מתאים לרכב כלשהו; הצמתים בגרף מסמנים משימות; יש קשת בין שני צמתים אם ורק אם אלו משימות ש"עולות" אחת על השנייה; הצבעים החוקיים לצביעת צומת ספציפית הם צבעי כל הרכבים שהפרמטרים שלהם מתאימים למשימה שהצומת מייצגת). |
|
|
|
|
|
|
||
|
||||
|
טוב, גם לי אין תשובה חד משמעית... :-) כנראה שזה ישאר פתוח. היתה לי איזו תקווה שמישהו מהקוראים ירים את הכפפה, יקח את הבעיה ואת הפתרון ויוכיח משהו. לא נורא. אני אעשה עוד נסיון אחד, להעלות את הניסוח הפורמלי, הן של הבעיה והן של האלגוריתם, אולי זה יעיר מישהו. :-| רן. |
|
|
|
|
|
|
||
|
||||
|
אולי הוא מתכוון ל-PCP? אמנם זו בעיה בלתי-כריעה, לא ב-NP, אבל... מכך שזה לא נכון, לא הייתי קופץ למסקנה שלא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
לא, לפי המשך השרשור, לא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שהבעיה נקראת staff scheduling ונהוג לפתור אותה עם integer programming. | |
|
|
|
|
|
||
|
||||
|
http://en.wikipedia.org/wiki/Linear_programming#Inte... היא בכלל בעיה NP קשה (כך שלא ממש נהוג לפתור אותה). | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת "לא ממש נהוג לפתור אותה"? | |
|
|
|
|
|
||
|
||||
|
לבעיות שמצריכות תכנון בשלמים, במקרה הכללי, אין פתרון ישים. | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת אין פיתרון ישים? ברור שיש פיתרונות, רק שלא תמיד הם אופטימליים. | |
|
|
|
|
|
||
|
||||
|
נדמה לי, ותקן אותי אם אני טועה, שהבעיה שהוצגה כאן היא בעיית אופטימיזציה. | |
|
|
|
|
|
||
|
||||
|
אכן. לבעיות אופטימיזציה שהן NP-קשות נהוג למצוא פתרונות מקורבים. יש תחום מחקרי שלם (ומרתק) על "עד כמה טוב אפשר לקרב בעיה מסויימת בלי לקבל ש-P=NP". מסתבר שבעיות NP-שלמות נבדלות זו מזו באופן דרסטי במידת הקירוב האפשרית שלהן. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |