סכמת קירוב פולינומית
סכמת קירוב פולינומית (PTAS) היא מחלקת סיבוכיות של בעיות אופטימיזציה להן ניתן למצוא פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב בסיבוכיות פולינומית לגודל הקלט בהתייחס ל$ \varepsilon $ כקבוע.
הגדרה
בעייה נמצאת במחלקת PTAS אם ורק אם קיים אלגוריתם קירוב שמקבל $ \varepsilon $ כלשהו וקלט לבעיה, כאשר $ OPT $ הוא הפתרון האופטימלי עבור קלט זה, ומחזיר תשובה שהיא לפחות $ (1-\varepsilon )*OPT $ עבור בעיית מקסימום או לא יותר מ $ (1+\varepsilon )*OPT $ עבור בעיית מינימום, בסיבוכיות פולינומית לגודל הקלט ובהתייחס ל$ \varepsilon $ כקבוע, מה שמאפשר שהאלגוריתם יהיה אקספוננציאלי ביחס ל$ 1/\varepsilon $.
מחלקה זאת היא תת קבוצה ממש של מחלקת הסיבוכיות APX שמאגדת את כל הבעיות שקיים להם אלגוריתם קירוב פולינומי, אלא אם כן P=NP מה שיגרור זהות בין הקבוצות.
סכמת קירוב פולינומית מלאה
תת קבוצה ממש (אלא אם כן P=NP) של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה (FPTAS). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב$ 1/\varepsilon $. קירוב כזה קיים לבעיית תרמיל הגב למשל[1].
קישורים חיצוניים
- Approximation Schemes – A Tutorial - שיטות ליצירת אלגוריתמי קירוב פולינומיים.
הערות שוליים
| מחלקות סיבוכיות חשובות (נוספות) | ||
|---|---|---|
| נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
| ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
| נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
| היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
| משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE | |
שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] סכמת קירוב פולינומית24481441