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