הוכיחו כי אם קיים אלגוריתם קירוב בעל יחס קירוב 1.49 לבעיית Bin-Packing, אז P=NP. **רמז:**…

שאלה פתוחהq-c36c23df63f3

נוסח השאלה

הוכיחו כי אם קיים אלגוריתם קירוב בעל יחס קירוב $1.49$ לבעיית $Bin\text{-}Packing$ , אז $P=NP$ .

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

נוסח מטלה שנבדק אנושית.

ייחוס מדויק

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

מטלה

2026א_05_תרגיל_5.md

שאלה 4עמוד 1נבדק אנושית

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

שיעור 13 · עמוד 2המשך בעיות NP קשות
מילים משותפותBin · Packing · Partition · בעיית