NP ו- P כמה שאלות
"הגדרות" לא פורמליות (הגרשיים הם משום שהגדרה חייבת להיות פורמלית):
P זו קבוצת הבעיות שניתן למצוא להן פתרון בזמן סביר.
NP זו קבוצת הבעיות שניתן לבדוק בזמן סביר האם פתרון מוצע כלשהו עבורן הוא אכן פתרון לבעיה.
ההגדרות הפורמליות הן:
L in P אם קיימת מכונת טיורינג דטרמיניסטית שמכריעה את L בזמן פולינומי.
(זמן פולינומי משמעותו שקיים פולינום q כך שלכל *x in Sigma מתקיים: zz |M(x)| <= q(|x|) zz (כאשר zz |M(x)| zz זה מספר הצעדים של M בריצת x).
L in NP אם קיימת מכונת טיורינג לא דטרמיניסטית שמכריעה את L בזמן פולינומי.
כעת, יש לי כמה שאלות:
1. הדימיון בין ההגדרה הלא פורמלית של P להגדרה הפורמלית של P מובן לי. אבל לא ברור לי הדימיון בין ההגדרה הלא פורמלית של NP להגדרה הפורמלית של NP. או במילים אחרות, למה הפירוש האינטואיטיבי של ההגדרה הפורמלית של NP, הוא ההגדרה הלא פורמלית של NP?
2. אינטואיטיבית, למה P מוכל ב-NP?
3. פורמלית, P מוכל ב-NP אם מראים שכל מכונת טיורינג דטרמיניסטית היא בפרט לא דטרמיניסטית.
כיצד מוכיחים שכל מכונת טיורינג דטרמיניסטית, היא לא דטרמיניסטית?
תודה מראש לעונים.
"הגדרות" לא פורמליות (הגרשיים הם משום שהגדרה חייבת להיות פורמלית):
P זו קבוצת הבעיות שניתן למצוא להן פתרון בזמן סביר.
NP זו קבוצת הבעיות שניתן לבדוק בזמן סביר האם פתרון מוצע כלשהו עבורן הוא אכן פתרון לבעיה.
ההגדרות הפורמליות הן:
L in P אם קיימת מכונת טיורינג דטרמיניסטית שמכריעה את L בזמן פולינומי.
(זמן פולינומי משמעותו שקיים פולינום q כך שלכל *x in Sigma מתקיים: zz |M(x)| <= q(|x|) zz (כאשר zz |M(x)| zz זה מספר הצעדים של M בריצת x).
L in NP אם קיימת מכונת טיורינג לא דטרמיניסטית שמכריעה את L בזמן פולינומי.
כעת, יש לי כמה שאלות:
1. הדימיון בין ההגדרה הלא פורמלית של P להגדרה הפורמלית של P מובן לי. אבל לא ברור לי הדימיון בין ההגדרה הלא פורמלית של NP להגדרה הפורמלית של NP. או במילים אחרות, למה הפירוש האינטואיטיבי של ההגדרה הפורמלית של NP, הוא ההגדרה הלא פורמלית של NP?
2. אינטואיטיבית, למה P מוכל ב-NP?
3. פורמלית, P מוכל ב-NP אם מראים שכל מכונת טיורינג דטרמיניסטית היא בפרט לא דטרמיניסטית.
כיצד מוכיחים שכל מכונת טיורינג דטרמיניסטית, היא לא דטרמיניסטית?
תודה מראש לעונים.