כל מה שרצית לדעת על PLS (סיבוכיות):
בתורת הסיבוכיות, מחלקת הסיבוכיות (PLS (Polynomial Local Search היא תת-מחלקה סינטקטית של מחלקת הסיבוכיות TFNP.
המחלקה הוגדרה על ידי כריסטוס פפדימטריו ב-1988 והבעיות הכלולות בה הן בעיות מקסימיזציה או מינימיזציה אשר מובטח כי יש להן פתרון.
כשמה, מתארת המחלקה PLS בעיות חיפוש אשר בהינתן קלט, מוגדרת לו קבוצה של פתרונות אפשריים – לכל פתרון יש מחיר, והמטרה היא מציאת פתרון במחיר אופטימלי מקומי.
על פי הגדרת הבעיה, לכל פתרון מוגדרת "סביבה" ("Neighborhood").
פתרון יחשב אופטימאלי באופן מקומי אם אין אף פתרון בסביבה שלו עם עלות טובה יותר.