תרגיל בית 6 שאלה 7א

תרגיל בית 6 שאלה 7א

student (guest) 27 Jul 2016 15:05

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

Re: תרגיל בית 6 שאלה 7א

Dean Doron 27 Jul 2016 18:39

That's right, because we didn't show a (many-one) reduction, as we did in class.
What is mentioned in the solution is what's called a Turing reduction, but there also exists a regular reduction (which shows NPC)
between these two languages, it's simply slightly harder.

student (guest) 27 Jul 2016 19:03

any clue? please