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

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

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

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

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

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

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

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

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

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

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