השאלה היא תחת ההנחה שP לא שווה NP.
בתרגיל מניחים בשלילה ששפה מסוימת שייכת לP ומראים שניתן לפתור את subsetsum בזמן פולינומי.
מה אפשר להסיק מהפתרון הזה?
מצד אחד, לא הוכחנו שהשפה שייכת לNPC (קל לראות שהיא שייכת לNP, והחלק הקשה הוא להראות שהיא NP-קשה).
מצד שני, אם היא שייכת לP אז P=NP (כי subsetsum בP והוא כן שייך לNPC)
ממה שאני מבינה, אי אפשר להסיק מהפתרון שהשפה שייכת לNPC, אבל
בכל זאת, "ממש נראה" כאילו היא כן שייכת לNPC. האם יש פתרון שמשתמש ברדוקציה? אפשר בבקשה לקבל אותו?
תרגיל בית 6 שאלה 7א