P = co-P
אני רוצה להוכיח את השיוויון הזה: P = co-NP.
השיוויון הזה, אומר בעצם ש-P סגורה תחת משלים. כלומר לכל שפה L in P, מתקיים L' in P (כאשר 'L זה המשלים של L).
כלומר במקום להוכיח הכלה דו-כיוונית, אני יכול להוכיח ש-P סגורה למשלים, וזה שקול לשיוויון P = co-P?
אנסה להראות ש-P סגורה למשלים.
תהי L in P שפה.
לכן קיימת מכונת טיורינג M דטרמיניסטית שמכריעה את L בזמן פולינומי.
במילים אחרות, קיים פולינום p ואלגוריתם A המאפשר להכריע את L בזמן (p(n.
(כאשר זמן פולינומי, פירושו שזמן הריצה של המכונה הוא פונקציה, החסומה ע"י פולינום כלשהו, של אורך הקלט)
צריך להוכיח L' in P.
כלומר יש להראות שקיימת מכונת טיורינג 'M דטרמיניסטית שמכריעה את 'L בזמן פולינומי.
נבנה אותה על סמך המכונה M שמכריעה את L בזמן פולינומי:
המכונה 'M תיהיה זהה למכונה M פרט למצבי העצירה. עבור מעבר ב-M שמסתיים במצב אישור, אותו מעבר יסתיים ב-'M, במצב דחייה.
עבור מעבר ב-M שמסתיים במצב דחייה, אותו מעבר יסתיים ב-'M, במצב אישור.
לכן P סגורה למשלים, ולכן P = co-NP.
האם ההוכחה הזו נכונה?
תודה מראש
אני רוצה להוכיח את השיוויון הזה: P = co-NP.
השיוויון הזה, אומר בעצם ש-P סגורה תחת משלים. כלומר לכל שפה L in P, מתקיים L' in P (כאשר 'L זה המשלים של L).
כלומר במקום להוכיח הכלה דו-כיוונית, אני יכול להוכיח ש-P סגורה למשלים, וזה שקול לשיוויון P = co-P?
אנסה להראות ש-P סגורה למשלים.
תהי L in P שפה.
לכן קיימת מכונת טיורינג M דטרמיניסטית שמכריעה את L בזמן פולינומי.
במילים אחרות, קיים פולינום p ואלגוריתם A המאפשר להכריע את L בזמן (p(n.
(כאשר זמן פולינומי, פירושו שזמן הריצה של המכונה הוא פונקציה, החסומה ע"י פולינום כלשהו, של אורך הקלט)
צריך להוכיח L' in P.
כלומר יש להראות שקיימת מכונת טיורינג 'M דטרמיניסטית שמכריעה את 'L בזמן פולינומי.
נבנה אותה על סמך המכונה M שמכריעה את L בזמן פולינומי:
המכונה 'M תיהיה זהה למכונה M פרט למצבי העצירה. עבור מעבר ב-M שמסתיים במצב אישור, אותו מעבר יסתיים ב-'M, במצב דחייה.
עבור מעבר ב-M שמסתיים במצב דחייה, אותו מעבר יסתיים ב-'M, במצב אישור.
לכן P סגורה למשלים, ולכן P = co-NP.
האם ההוכחה הזו נכונה?
תודה מראש