רדוקציות הן טומאה ותועבה הן מזוהמות, רקובות , ארורות , שיקוץ עלי אדמות. אני צריך להוכיח ש- \3DM היא בעיית NPC. למי שלא מכיר את הבעיה- יש לנו n גברים ו-n נשים שרוצים להתחתן. יש לנו רשימה של הזוגות שמוכנים להתחתן ביחד. השאלה היא האם ניתן לחתן את כל n הזוגות מבלי לחרוג מהרשימה הזו. 3DM היא בדיוק אותו דבר, רק עם שלושה קבוצות של איברים, במקום שתי קבוצות(גברים ונשים). אני די בטוח שהרדוקציה צריכה להיות עם 3SAT אבל פשוט לא הצלחתי לקשר שבחירה של קבוצה תהווה בחירה של ליטרל\סיפוק של הסגר. כיוון נוסף שהיה לי הוא לנסות לעוות את exact match , כיוון שהשאלות דומות רק שב3DM ישנה הגבלה שכל קבוצה בגודל 3 איברים וה-U שלנו גם הוא מתחלק לשלוש. ניסיתי לפרק כל קבוצה ב- exact match לקבוצות מהצורה של 3DM כך שאם נבחר לקחת את אחת הקבוצות שמייצגת חלק מקבוצה ב exact match, נהיה חייבים לקחת את כל הקבוצות שמייצגות את אותה קבוצה. הבעיה עם זה שלא הצלחתי לסדר שה-U יתחלק לשלושה חלקים בגודל שווה =\ אני מניח שהניסיונות שלי די חסרי טעם ._. .. מישהו יכול לרשום או להפנות אותי לרדוקציה שאיתה מוכיחים NPC של 3DM? או אולי לתת לי כיוון? המקום היחיד שהבנתי שיש בו את הרדוקציה הוא הספר של ג'ונסון על NP , אבל אין לי את הספר, אין אותו בספרייה ובאינטרנט הצלחתי להשיג רק 45 אחוז ממנו P: וואו. כמה רשמתי רק בשביל לבקש רדוקציה ל 3DM O.O