הצגת המקור של הדף "APX"

'''APX''' (קיצור המילה ה[[אנגלית]] Approximable, ניתן לקירוב) היא [[מחלקת סיבוכיות]] של בעיות אופטימיזציה להן ניתן למצוא פתרון מקורב על ידי [[אלגוריתם קירוב]] בסיבוכיות פולינומית.

== הגדרת המחלקה ==
ידוע כי קיימות ב[[NP (מחלקת סיבוכיות)|מחלקת הבעיות NP]], בעיות הקשות לפחות כמו כל שאר הבעיות במחלקה (בעיות [[NP (מחלקת סיבוכיות)#בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC)|NP-שלמות]]). מבעיות אלה נגזרות בעיות אופטימיזציה שונות (בעיות המחלקה NPO), אשר כולן בלתי נתנות לפתרון בזמן פולינומי אלא אם כן [[בעיית P=NP|P=NP]], כלומר - לכל הבעיות השייכות ל-NP קיים פתרון פולינומי.

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

ניתן לזהות שני סוגי בעיות אופטימיזציה ב-NPO:
* בעיות להן ניתן למצוא אלגוריתם פולינומי עבור יחס קירוב <math>\ 0 < \varepsilon < 1</math> כלשהו. (בעיות אלה שייכות למחלקה APX)
* בעיות להן ניתן למצוא אלגוריתם פולינומי לכל יחס קירוב <math>\ 0 < \varepsilon < 1</math> בהתייחס אל <math>\  \varepsilon  </math> בתור קבוע, ולכן עלול להיות אקספוננציאלי ביחס ל <math>\ 1/ \varepsilon  </math>. אוסף אלגוריתמים פולינומיים כאלה מכונה [[סכמת קירוב פולינומית]] (באנגלית: Polynomial Time Approximation Scheme, ובקיצור PTAS). המחלקה המאגדת בעיות אלה קרויה PTAS.

בבירור מתקיים:
: <math>\ PTAS\subseteq APX\subseteq NPO</math>

אי השוויון השמאלי מתקיים כשוויון אם ורק אם <math>\ P=NP</math>.

== דוגמאות ==
=== [[בעיית הספיקות המרבית]] ===
בעיית הספיקות המרבית היא בעיית מציאת השמת ערכי אמת עבור נוסחה בוליאנית הנתונה בצורת [[CNF]] עבורה יסופק מספר מרבי של פסוקיות.

בעיה זו שייכת ל-APX ואינה שייכת ל-PTAS. (אלא אם כן [[P=NP]]{{הערה|J. Håstad, '''[http://citeseer.ist.psu.edu/506917.html Some optimal inapproximability results]''', Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10}})

בעיה זו גם '''APX-שלמה''', כלומר: קיימת [[רדוקציה משמרת קירוב]] ממנה לכל בעיה ב-APX.

=== [[בעיית קבוצת קודקודי המשוב]] ===
בעיית קבוצת קודקודי המשוב היא בעיה בהינתן גרף ומספר טבעי k האם קיימת קבוצת משוב (קבוצת קודקודים בגרף שהסרתם מהגרף תיצור גרף ללא מעגלים) בגרף הנתון בגודל k?

בעיה זו היא APX-שלמה.

== ראו גם ==
* [[רדוקציה משמרת קירוב]]

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}
{{מחלקות סיבוכיות}}

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