PLS (סיבוכיות)

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

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

מוטיבציה

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

בעיית PLS כללית

תהי בעיה L (לדוגמה, בעיית הסוכן הנוסע – בעיית מינימיזציה). L נתונה על ידי קבוצת איברים D (ערים בהן יש לעבור), לכל איבר $x\in D$ קיים סט סופי $F(x)\$ של פתרונות (מסלולים אפשריים העוברים בכל הערים) כל אחד מהם חסום פולינומית. לכל פתרון $s\in F(X)$ , קיימת עלות אי שלילית $c(s)\$ (עלות הנסיעה במסלול) ורשימת שכנים $N(s)\subseteq F(x)$ אשר תקרא הסביבה של פתרון s (תלוי בהגדרת יחס השכנות, לדוגמה עבור מסלול s נגדיר כי מסלול s' הוא שכן מסדר k אם בהצגת s ו – s' כמחרוזות, מרחק העריכה מ – s ל– s' הוא 2k). על האלגוריתם למצוא פתרון אופטימלי מקומי, כלומר בהינתן L על האלגוריתם למצוא פתרון s אשר לא קיים לו שכן s' מסדר 1 אשר עלותו נמוכה יותר (כלומר שלכל $s'\in N(s)$ מתקיים ( $\ C(s)\leq C(s')$ ).

פתרון כללי לבעיית PLS

ראשית נשים לב שכיוון שלכל x הדרישה היא כי הקבוצות D וכן $F(x)|(x\in D)$ הן סופיות אזי קבוצת הפתרונות חסומה ולכן בהכרח קיים לה מקסימום, כלומר לבעיית PLS קיים תמיד פתרון. על מנת לפתור את הבעיה נניח קיום של 3 אלגוריתמים שזמן ריצתם פולינומי באורך הקלט.

A – בהינתן $x\in D$ (רשימת ערים), A מחזיר פתרון כלשהו ל – x (מסלול כלשהו אשר עובר בכל הערים).

B – בהינתן x (רשימת ערים בהן יש לעבור) ומחרוזת s (סדר כלשהו של מעבר בין ערים) B יבדוק האם s הנו פתרון ל – x (האם s מתאר מעבר חוקי על כל הערים ב – x) ואם כן יחזיר את עלותו $\ c(x)$ .

C – בהינתן פתרון s, יחזיר פתרון מקבוצת השכנים של s שעלותו נמוכה יותר מזו של s או כי לא קיים כזה – כלומר s הוא אופטימום מקומי. פתרון כללי לבעיה יהיה :

PLSSolver(A,C,D)                  // A,C algorithms as described and the group D
 s = A(x)                         // Let s be some arbitraty initial solution
 While C(s) != local optimum      // If s is still not a local optimum
    s = C(x)                      // Generate a better solution from s's neighbors or state it is a local optimum

רדוקציות ב – PLS ו שלמות ב – PLS

בעיה – L ב - PLS היא PLS שלמה (PLS-Complete) אם לכל בעיה ב – PLS קיימת רדוקציה ל – L.

בעיה L ב – PLS ניתנת לרדוקציית PLS לבעיה K נוספת (PLS-reducible) אם קיימות פונקציות f,g בעלות זמן ריצה פולינומי המקיימות:

f ממפה איברים מ – L לאיברים של K.
בהינתן $x\in L$ ופתרון ל – $\ f(x)$ , הפונקציה g ממפה את הזוג((x, solution of f(x) לפתרון של x.
לכל איבר $x\in L$ , אם s הוא אופטימום מקומי עבור $\ f(x)$ , אזי $\ g(s,x)$ הוא אופטימום מקומי עבור x.