מישהו...עזרה עם זה..

[student47]

מישהו...עזרה עם זה..

הגדרה: שפה L תיקרא NP-קשה אם לכל שפה L' in NP מתקיים שיש רדוקציה פולינומית מ-'L ל-L.
הגדרה: שפה L תיקרא NP-שלמה אם L in NP, ובנוסף L שפה NP-קשה.

טענה:
שפה L היא NP-קשה אם ורק אם קיימת שפה NP-קשה 'L כך שיש רדוקציה פולינומית מ-'L ל-L.

אני מנסה להוכיח את הטענה הזו. עם הכיוון משמאל לימין אני חושב שאני מסתדר. עם הכיוון מימין לשמאל פחות. ארשום את מה שעשיתי עד עכשיו:
כיוון משמאל לימין:
'L שפה NP-קשה ולכן יש רדוקציה פולינומית מכל השפות ב-NP אל 'L.
כלומר מתקיים: zz for each L'' in NP: L'' <= L' zz (כאשר 'L'' <= L פירושו: רדוקציה פולינומית מ-''L אל 'L).
ידוע: zz L' <= L zz.
מטרנזיטיביות של רדוקציות פולינומיות אקבל: zz for each L'' in NP: L'' <= L zz.
מכאן שיש רדוקציה פולינומית מכל השפות ב-NP לשפה L ולכן L היא שפה NP-קשה.

כיוון מימין לשמאל: למען האמת אני תקוע כאן..רק התחלתי כך:
L היא שפה NP-קשה.
לכן לכל שפה L' in NP מתקיים: L' <= L.
זאת אומרת שמכל השפות ב-NP יש רדוקציה פולינומית לשפה L. על מנת לסיים, אני צריך להוכיח שאחת מאותן שפות, היא NP-קשה? אם כן, כיצד מראים זאת?

אודה על עזרתכם

 

[1ca1]

חבר, אתה צריך לחשוב טיפה מעבר

אין תחליף ללימוד מאשר לשבת ולחזור על ההגדרות וליישם אותן בשיעורי הבית. אני מציע גם להיעזר במתרגל של הקורס במידת הצורך.
&nbsp
הכיוון היותר קשה הוא דווקא הכיוון שהוכחת.
הכיוון שאתה שואל עליו הוא מיידי.
אם שפה L היא NP-Hard אז בהגדרה לכל שפה NP נניח L' יש רדוקציה פולינומיאלית אליה.
בפרט בהינתן שפה כזו L' (שיכולה להיות NP-שלמה או קשה או משהו, לא איכפת לי), אז מההגדרה של L יש רדוקציה אליה.
זהו. זה נתון מיותר.
בעצם השאלה היא האיפיון של שפה NP-Hard משמאל לימין וזהו (אני בטוח שהדיון בהמשך ידבר על 3SAT ואיך מוכיחים שהיא NP-Hard דרך כתיבת נוסחאות לוגיות).