נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה φ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ו…

נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה $φ$ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ופונקציית משקל w המתאימה משקל חיובי לכל הסגר בנוסחה. מטרה: למצוא השמה המקיימת כי משקל ההסגרים המסופקים הוא מקסימלי. יהי $φ, w$ קלט לבעיה, ונסמן ב W את סך כל המשקלים בגרף, כלומר$, W = Σ_{C\in φ} w(C)$. מהו הערך הגדול ביותר $α \in [0,1]$ עבורו ידוע שקיימת השמה שבה משקל ההסגרים המסופקים הוא לפחות $αW$ ! שימו לב כי עבור הערך שתבחרו יש להוכיח כי לכל קלט קיימת השמה קלט כדרוש, וגם קיים קלט עליו לא קיימת השמה המספקת משקל גדול יותר של הסגרים.