נתבונן באלגוריתם המקבל כקלט גרף לא מכוון G = (V,E) ומחזיר כפלט: • גרף שלם לא מכוון עם משקלים על הקשתות G = (V,…

נוסח השאלה

1. א

   אם $x = 0, y = 1, k = 0$, אז האלגוריתם מהווה רדוקציית זמן פולינומי מ-UHC ל- TSP .

2. ב

   אם $x = 0, y = 1, k = 0$, אז האלגוריתם מהווה רדוקציית זמן פולינומי מ-UHC ל-TSP-TI.

3. ג

   אם $x = 1, y = 0, k = 0$, אז האלגוריתם מהווה רדוקציית זמן פולינומי מ-UHC ל- $\overline{TSP}$.

4. ד

   אם $x \geq 1, y = x + 1, k = x \bullet |V|$, אז האלגוריתם מהווה רדוקציית זמן פולינומי מ-UHC

5. התשובות א ', ד ' נכונות.
6. ויש בדיוק תשובה אחת שגויה בסעיפים א-ד.