1. נגדיר אלגוריתם לבעיית BinPacking כלהלן: בהינתן קלט a 1, ,a n, האלגוריתם עובר על כל מספר ברשימה לפי הסדר הנת…

נגדיר אלגוריתם לבעיית $BinPacking$ כלהלן: בהינתן קלט $a_1,\ldots,a_n$, האלגוריתם עובר על כל מספר ברשימה לפי הסדר הנתון; במידת האפשר הוא מכניס אותו לתא האחרון שנעשה בו שימוש, ואחרת מכניס אותו לתא חדש.

1. הוכיחו כי בכל חלוקה לתאים שמחשב האלגוריתם, סכום האיברים שהוכנסו לשני תאים סמוכים גדול מ-$1$.
2. הוכיחו כי האלגוריתם משיג יחס קירוב $2$.

הוכיחו כי אם קיים אלגוריתם $1.49$-קירוב בזמן פולינומיאלי לבעיית $BinPacking$, אז $P=NP$.

הדרכה: השתמשו בכך שהשפה $Partition$ היא $NP$-קשה.