האם אני צודק?

[student47]

האם אני צודק?

בתשובות שלי לשתיי השאלות הבאות:

הוכח: אם יש רדוקציה פולינומית מ-A ל-B ו-B in P, הרי שגם A in P.
הוכחה:
B in P ולכן קיים אלגוריתם דטרמיניסטי M ופולינום p כך ש-M מכריע את B בזמן החסום ע"י p.
בנוסף, קיימת רדוקציה R מ-A ל-B, ניתנת לחישוב בזמן חסום ע"י פולינום q.

נבנה אלגוריתם D להכרעת A:
(D(x:
1. חשב את (R(x ושים את התוצאה במשתנה y.
2. הפעל את (M(y.

הסיבה ש-D מכריע את A נובעת מכך שרדוקציה היא פונקציה שמקיימת לכל *x in Sigma מתקיים: x in A אם ורק אם f(x) in B.

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

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

לשפה NP שלמה יש אלגוריתם ל"ד פולינומי שמכריע אותה.
מדוע מציאת אלגוריתם דטרמיניסטי פולינומי עבור שפה כזו, יגרור קיום של אלגוריתם כזה עבור כל שפה ב-NP?

אנסה לענות:

תהי L שפה NP שלמה כלשהי. מאחר והיא ב-NP קיים אלגוריתם ל"ד פולינומי שמכריע אותה.
כמו כן, מאחר והיא NP שלמה, מתקיים שלכל שפה L' in NP יש רדוקציה פולינומית מ-'L ל-L.
נניח כעת שעבור L יש אלגוריתם דטרמיניסטי פולינומי שמכריע אותה, זאת אומרת L in P.
לכן מהטענה הקודמת נובע: L' in P.
כלומר יוצא שלכל L' in NP מתקיים: קיים אלגוריתם דטרמיניסטי פולינומי שמכריע את 'L.

המסקנה היא שאם החיתוך של קבוצת השפות ה-NP-קשות ושל הקבוצה P אינו ריק, אזי בה"כ L שפה ששייכת לחיתוך זה.
מהאמור לעיל, אקבל שלכל שפה 'L ב-NP קיים אלגוריתם דטרמיניסטי פולינומי שמכריע אותה, שזה אומר ש-P=NP.

אשמח אם מישהו יוכל בבקשה לומר האם כל מה שכתבתי כן מדוייק.

תודה מראש.