תרגיל

הרכבת רדוקציות פולינומיאליות

הוכחת טרנזיטיביות תוך התחשבות באורך פלט הביניים.

מקורות מטלות

מטלות סמסטר א׳ 2026מטלה רשמיתexercise3.pdfQ1מסמך קורס סמכותי

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 3 - סיבוכיות.pdfQ1הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

הקישורים מציינים התאמה רעיונית או גרסה קרובה; רק קבוצות שמסומנות כחזרה מדויקת במפת השאלות נחשבות לכפילויות.

נניח $A\le_m^p B$ באמצעות $f$ , וכן $B\le_m^p C$ באמצעות $g$ . הוכיחו $A\le_m^p C$ , כולל ניתוח אורך $f(x)$ .

איזו הרכבת פונקציות ממפה מופע של $A$ ישירות למופע של $C$ ?

אם $f$ רצה בזמן $p(n)$ , היא אינה יכולה לכתוב יותר מ- $p(n)$ סימנים. הציבו חסם זה בפולינום הזמן של $g$ .

נגדיר $h(x)=g(f(x))$ . הנכונות מתקבלת מן השרשרת

x\in A\iff f(x)\in B\iff g(f(x))\in C.

נניח שזמן $f$ הוא $p(n)$ וזמן $g$ על קלט באורך $m$ הוא $q(m)$ . עד כדי קבוע של מודל המכונה, $|f(x)|\le p(|x|)$ . לכן

T_h(n)\le p(n)+q(p(n)),

וזהו פולינום. מכאן ש- $h$ היא רדוקציית many-one פולינומיאלית.

לא די לומר ששני אלגוריתמים פולינומיאליים הופעלו; יש לחסום גם את אורך מופע הביניים.

זהו ניסוח מקורי של הוכחת הטרנזיטיביות הסטנדרטית לפי הגדרות ספרי הלימוד. פתרונות סטודנטים אינם מקור סמכות.

Merged summary, pp. 43-49
2026 transcript 9
Sipser 3e, sec. 7.4
מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הבעיה הקשה הידועה Aמופע המקור x

f(x)מהדר פולינומי כולל

פותר לבעיית היעד Bאלגוריתם מהיר היפותטי

תשובת כן/לא של הפותר מכריעה את A