APX

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

הגדרת המחלקה

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

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

ניתן לזהות שני סוגי בעיות אופטימיזציה ב-NPO:

• בעיות להן ניתן למצוא אלגוריתם פולינומי עבור יחס קירוב $\ 0<\varepsilon <1$ כלשהו. (בעיות אלה שייכות למחלקה APX)
• בעיות להן ניתן למצוא אלגוריתם פולינומי לכל יחס קירוב $\ 0<\varepsilon <1$ בהתייחס אל $\ \varepsilon$ בתור קבוע, ולכן עלול להיות אקספוננציאלי ביחס ל $\ 1/\varepsilon$. אוסף אלגוריתמים פולינומיים כאלה מכונה סכמת קירוב פולינומית (באנגלית: Polynomial Time Approximation Scheme, ובקיצור PTAS). המחלקה המאגדת בעיות אלה קרויה PTAS.

בבירור מתקיים:

$\ PTAS\subseteq APX\subseteq NPO$

אי השוויון השמאלי מתקיים כשוויון אם ורק אם $\ P=NP$.

דוגמאות

בעיית הספיקות המרבית

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

בעיה זו שייכת ל-APX ואינה שייכת ל-PTAS. (אלא אם כן P=NP)

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

בעיית קבוצת קודקודי המשוב

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

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

ראו גם

• רדוקציה משמרת קירוב