P (מדעי המחשב)

מתוך ויקיפדיה, האנציקלופדיה החופשית

במדעי המחשב, מחלקת הבעיות P היא קבוצת כל בעיות ההכרעה אשר ניתנות לפתרון באופן יעיל, דהיינו בזמן ריצה פולינומיאלי.

ידוע כי P מכילה בעיות נפוצות רבות. למשל, הבעיה של תכנון לינארי, חישוב המחלק המשותף המקסימלי של שני מספרים טבעיים, חישוב עץ פורש מינימלי ומציאת שידוך מקסימום בגרף. בשנת 2002 התגלה כי גם הבעיה של הכרעה האם מספר כלשהו הוא ראשוני שייכת ל-P.

[עריכה] מוטיבציה להגדרה

הבחירה לזהות את מושג החישוב היעיל עם אלגוריתמים שזמן ריצתם פולינומי אינה שרירותית, ויש לה מספר סיבות שונות.

ראשית, כל אלגוריתם שקורא את כל הקלט שקיבל הוא בעל סיבוכיות זמן ריצה לינארית לכל הפחות (כלומר, זמן ריצתו המינימלי הוא קבוע כפול גודל הקלט). אף שקיימים אלגוריתמים שאינם תלויים בכל הקלט, הם לרוב מבוססים על ביצוע פעולות על מבנה נתונים קיים (למשל, חיפוש בעץ חיפוש) שהיה צורך לקרוא את תוכנו על מנת ליצור אותו מלכתחילה, ולכן עיקר העניין הוא באלגוריתמים שצריכים לקרוא את הקלט כולו.

עם זאת, סיבוכיות זמן ריצה לינארית היא קטנה מדי לרוב השימושים המעשיים. לדוגמה, אלגוריתם מיון לקלט כללי דורש זמן ריצה גדול יותר מזמן ריצה לינארי, טרם התגלה אלגוריתם כללי לחישוב עץ פורש מינימלי הפועל בזמן ריצה לינארי, וכדומה. נוסף על כך, זמן ריצה לינארי יוצר בעיות של רגישות למודל התיאורטי שבו משתמשים כדי להעריך את סיבוכיות זמן הריצה: לדוגמה, ישנן בעיות שניתנות להכרעה בזמן לינארי באמצעות מכונת טיורינג עם מספר סרטים, אבל לא עם מכונת טיורינג בעלת סרט אחד.

הבחירה להרחיב את מחלקת הפונקציות שנחשבות לזמן ריצה יעיל לכל הפונקציות הפולינומיות מקנה יתרונות אחדים:

  1. הרגישות למודל החישוב נעלמת - בעיה שדורשת זמן ריצה פולינומי במחשב דורשת זמן ריצה פולינומי גם במכונת טיורינג דטרמינסיטית חד-סרטית.
  2. רובם המכריע של האלגוריתמים שנחשבים יעילים הם בעלי זמן ריצה פולינומי.
  3. חישובים בעלי סיבוכיות זמן ריצה פולינומית ניתנים להרכבה: כלומר, אם ניתן לפתור את בעיה א' בזמן ריצה פולינומי וניתן להפוך בעיה מסוג ב' לבעיה מסוג א' בזמן ריצה פולינומי, אז ניתן לפתור את בעיה ב' גם כן בזמן ריצה פולינומי על ידי הפיכתה לבעיה מסוג א' (דרך פתרון זו מכונה רדוקציה חישובית).

[עריכה] הגדרה פורמלית

אחת ההגדרות הפורמליות הנפוצות ל-P משתמשת במושג המתמטי של מכונת טיורינג. אם עבור בעיית הכרעה קיימת מכונת טיורינג דטרמיניסטית שמכריעה את הבעיה (כלומר, עוצרת תמיד ומחזירה תשובה חיובית או שלילית נכונה), נהוג להתעניין גם בזמן הריצה של מכונה זו. צורת המדידה המקובלת לזמן הריצה היא מספר הצעדים שהמכונה מבצעת.

מכיוון שקלטים גדולים יותר גוררים לרוב זמן ריצה ארוך יותר, נהוג לחשב את גודל זמן הריצה ביחס לגודל הקלט. מכיוון שקלט למכונת טיורינג נתון בתור סדרה של סימנים על הסרט, המדד המקובל הוא מספר הסימנים שמופיעים בקלט.

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

בתוך המחלקה P מבחינים בין בעיות להן קיים פתרון יעיל ומעשי, לבין כאלו שסיבוכיותם חסומה על ידי פולינום מדרגה גבוהה מאוד (לדוגמה \ n^{100000}).

[עריכה] יחס למחלקות אחרות

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