הצגת המקור של הדף "PLS (סיבוכיות)"

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

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

== מוטיבציה ==

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

== בעיית PLS כללית ==

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

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

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

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

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


<div style="direction: ltr;">
 '''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

</div>


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

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

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

== ראו גם ==
* [[PPAD (מחלקת סיבוכיות)]]
* [[:en:TFNP|TFNP]] 

== קישורים חיצוניים ==
* [http://faculty.cs.tamu.edu/chen/courses/637/2004/pres/pre2.pdf מצגת הסבר קצרה] {{Webarchive|url=https://web.archive.org/web/20040929205902/http://faculty.cs.tamu.edu/chen/courses/637/2004/pres/pre2.pdf |date=2004-09-29 }} - '''?How Easy Is Local Search''' 
* [http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf מאמר עמ' 318-319] - '''On total function, theorems and computational complexity''' 
* [https://web.archive.org/web/20081204124245/http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pls הערך PLS ב - Complexity zoo]

[[קטגוריה:מחלקות סיבוכיות]]