בעיית P=NP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←המחלקות P ו-NP: הגהה תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
Michael4123 (שיחה | תרומות) הערך מתאר את אחת הבעיות החשובות ביותר במדעי המחשב התאורטי, אשר חלק ניכר מהמחקר בתורת הסיבוכיות עוסק בו, ועל כן לדעתי יש לעבות אותו בפרטים רבים נוספים. |
||
שורה 29:
עם זאת, כלל לא ברור כי בהינתן קבוצה של מספרים, ניתן '''למצוא''' באופן יעיל חלוקה לשתי קבוצות שסכומן זהה. יותר סביר להניח, ואכן זוהי ההשערה הרווחת, כי כל אלגוריתם עלול להזדקק למספר גדול יותר של צעדים (למשל: לעבור על חלק גדול מהחלוקות האפשריות, שמספרן תלוי [[פונקציה מעריכית|אקספוננציאלית]] במספר האיברים בקבוצה).
==ההיררכיה הפולינומית==
{{הפניה לערך מורחב|ערכים=[[ההיררכיה הפולינומית]]}}
לאור הדעה הרווחת כי NP מכילה ממש את P, ומשום הקושי הרב שחווים בהוכחת (או הפרכת) הטענה, המחקר בסיבוכיות עוסק בעיקר בווריאציות שונות של הבעיה. אחת הווריאציות המוכרות והבסיסיות ביותר היא ההיררכיה הפולינומית (מסומנת PH).
הגדרת המחלקה NP בעזרת מכונות טיורינג שאינה דטרמיניסטית אינה הגדרה יחידה, וניתן להגדיר את המחלקה על ידי שימוש ב[[כמתים || כמת]]. את המחלקה NP נגדיר באמצעות הכמת "קיים פתרון" או "קיים פתרון מתקבל". את המחלקה המשלימה co-NP נגדיר באמצעות הכמת "לא קיים פתרון", או באופן קנוני יותר, "כל פתרון אפשרי אינו מתקבל". מכאן ההרחבה להיררכיה הפולינומית טריוויאלית במונחי כמתים - נוסיף שרשראות של כמתים, כלומר, במקום "קיים" (<math>\exists</math>) או "לכל" (<math>\forall </math>), נגדיר שרשראות של כמתים, לדוגמה <math>\exists \forall \exists</math>. כמובן שאין טעם בלשים כמתים מאותו סוג בצמידות.
הגדרת ההיררכיה מתקבלת ישירות מההגדרה על פי כמתים - בדרגה ה-i בהיררכיה, תופענה מחלקות הסיבוכיות עם i כמתים. נשים לב שיש בדיוק 2 מחלקות בכל דרגה, המסומנות <math>\Sigma_i, \Pi_i </math>. ההיררכיה נקראת פולינומית מכיוון שכל אחד מהערכים הקשורים (כלומר, הערכים הנמצאים בצמידות לכמת) מוגבלים להיות באורך פולינומי באורך הקלט. ההיררכיה נקראת היררכיה מכיוון שכל המחלקות בדרגה ה-<math>i-1 </math> מוכלות במחלקה שבדרגה ה-i. נשים לב, שבהצגה זו [[SAT]] היא באופן טריוויאלי שפה NP-שלמה.
הקרסת ההיררכיה היא הוכחה שעבור דרגה מסוימת בהיררכיה, מתקיים <math>\Sigma_i=\Pi_i </math>, אזי <math>PH=\Sigma_i=\Pi_i </math>. משפט זה שימושי מסיבות רבות. באופן מופשט - אם נוכיח שההיררכיה אינה קורסת תחת דרגה מסויימת, אזי <math>P\neq NP</math>.
משפט הקרסת ההיררכיה שימושי באופן נוסף - מספיק להוכיח ש-<math>P \neq \Sigma_i</math>, והתוצאה המיידית היא ש-P שונה מ-NP.
==ראו גם==
| |||