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[1])

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ J. Håstad, Some optimal inapproximability results, Proc. 28th Annual ACM Symp. on Theory of Computing (1997), El Paso, Texas, pp. 1-10