ריפוד משנה את אורך הקלט הנמדד

קישור שפה לגרסה מרופדת בלי לבלבל בין ערך לאורך.

שאלה

תהי $L$ שפה הניתנת להכרעה בזמן $2^{n^k}$ עבור $k\ge1$ קבוע. נגדיר, מעל אלפבית הכולל מפריד $\#$,

הוכיחו $L_{\mathrm{pad}}\in\mathrm P$ וציינו מה עושים בקלט פגום.

רמז 1

אם אורך הקלט המרופד הוא $N$, השוו את $2^{|x|^k}$ ל-$N$.

רמז 2

אפשר לבדוק את מספר האפסים בסריקה עם מונים באורך $O(\log N)$.

פתרון מלא

על קלט $w$ באורך $N$, בודקים שיש מפריד יחיד ומקבלים תחילית $x$ וסיומת אפסים. דוחים אם הצורה פגומה. מחשבים את $|x|^k$ ובודקים שאורך הסיומת הוא בדיוק $2^{|x|^k}$; הסריקה והספירה פולינומיאליות ב-$N$.

אם הקלט תקין, מדמים את המכריע של $L$ על $x$. זמן הריצה הוא

כי בקלט עצמו מופיעים אפסי ריפוד רבים כל כך. לכן הבדיקה והסימולציה יחד פולינומיאליות ב-$N$, ומתקבל $L_{\mathrm{pad}}\in\mathrm P$.

נקודת בדיקה

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

הערת מקור

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

טעויות נפוצות

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

מקורות ואימות

• Merged summary, pp. 124-130
• 2026 transcript 6
• Arora-Barak draft, padding discussion
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

פתיחה בגלריית ההמחשות: טיעון ריפוד