APX

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

הגדרת המחלקה

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

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

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

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

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

$\ PTAS\subseteq APX\subseteq NPO$

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

דוגמאות

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

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

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

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

ראו גם

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

21860633APX