P (מחלקת סיבוכיות)

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

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

מוטיבציה להגדרה

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

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

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

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

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

הגדרה פורמלית

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

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

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

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

יחס למחלקות אחרות

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