בשאלה זו נוכיח כי בעיית Bin-Packing שראינו בשיעור היא NP-שלמה. הקלט הוא סדרת מספרים a 1,a 2, ,a n (0,1] ומספר…

בשאלה זו נוכיח כי בעיית $Bin\text{-}Packing$ שראינו בשיעור היא $NP$-שלמה. הקלט הוא סדרת מספרים $a_1,a_2,\ldots,a_n\in(0,1]$ ומספר טבעי $k$. השאלה היא האם ניתן לחלק את המספרים ל-$k$ תאים כך שסכום המספרים בכל תא הוא לכל היותר $1$.

1. הוכיחו כי $Bin\text{-}Packing\in NP$.

2. נגדיר את האלגוריתם הבא.

   קלט: סדרת מספרים טבעיים $a_1,\ldots,a_n$ בייצוג עשרוני.

   1. נחשב $$\sum_{i=1}^{n}a_i$$ ונסמן את הסכום ב-$S$.
   2. אם קיים $i\in[n]$ כך ש-$a_i>S/2$, נחזיר את סדרת המספרים $$\frac34,\frac34,\ldots,\frac34$$ ואת המספר $2$.
   3. אחרת נחזיר את סדרת המספרים $$\frac{2a_1}{S},\frac{2a_2}{S},\ldots,\frac{2a_n}{S}$$ ואת המספר $2$.

   הוכיחו כי האלגוריתם מתאר רדוקציית זמן פולינומי מ-$Partition$ ל-$Bin\text{-}Packing$, והסיקו כי $Bin\text{-}Packing\in NP\text{-}hard$.