APX
APX (קיצור המילה האנגלית Approximable, ניתן לקירוב) היא מחלקת סיבוכיות של בעיות אופטימיזציה להן ניתן למצוא פתרון מקורב על ידי אלגוריתם קירוב בסיבוכיות פולינומית.
הגדרת המחלקה
עריכהידוע כי קיימות במחלקת הבעיות NP, בעיות הקשות לפחות כמו כל שאר הבעיות במחלקה (בעיות NP-שלמות). מבעיות אלה נגזרות בעיות אופטימיזציה שונות (בעיות המחלקה NPO), אשר כולן בלתי נתנות לפתרון בזמן פולינומי אלא אם כן P=NP, כלומר - לכל הבעיות השייכות ל-NP קיים פתרון פולינומי.
למרות שכל הבעיות ה-NP-שלמות קשות באותה המידה, מבחינת קיומו של פתרון פולינומי עבורן, בעיות האופטימיזציה הנגזרות מהן עשויות להיות שונות זו מזו באפשרות למצוא להן פתרונות מקורבים בזמן פולינומי.
ניתן לזהות שני סוגי בעיות אופטימיזציה ב-NPO:
- בעיות להן ניתן למצוא אלגוריתם פולינומי עבור יחס קירוב כלשהו. (בעיות אלה שייכות למחלקה APX)
- בעיות להן ניתן למצוא אלגוריתם פולינומי לכל יחס קירוב בהתייחס אל בתור קבוע, ולכן עלול להיות אקספוננציאלי ביחס ל . אוסף אלגוריתמים פולינומיים כאלה מכונה סכמת קירוב פולינומית (באנגלית: Polynomial Time Approximation Scheme, ובקיצור PTAS). המחלקה המאגדת בעיות אלה קרויה PTAS.
בבירור מתקיים:
אי השוויון השמאלי מתקיים כשוויון אם ורק אם .
דוגמאות
עריכהבעיית הספיקות המרבית היא בעיית מציאת השמת ערכי אמת עבור נוסחה בוליאנית הנתונה בצורת CNF עבורה יסופק מספר מרבי של פסוקיות.
בעיה זו שייכת ל-APX ואינה שייכת ל-PTAS. (אלא אם כן P=NP[1])
בעיה זו גם APX-שלמה, כלומר: קיימת רדוקציה משמרת קירוב ממנה לכל בעיה ב-APX.
בעיית קבוצת קודקודי המשוב היא בעיה בהינתן גרף ומספר טבעי k האם קיימת קבוצת משוב (קבוצת קודקודים בגרף שהסרתם מהגרף תיצור גרף ללא מעגלים) בגרף הנתון בגודל k?
בעיה זו היא APX-שלמה.
ראו גם
עריכההערות שוליים
עריכה- ^ J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10