Padding Changes the Measured Input Length

Relate a language to a padded version without confusing value and length.

Problem

Let $L$ be decidable in time $2^{n^k}$ for a fixed $k\ge1$. Over an alphabet containing a separator $\#$, define

Show that $L_{\mathrm{pad}}\in\mathrm P$. Clearly state how malformed padded strings are handled.

Hint 1

If the full padded input has length $N$, compare $2^{|x|^k}$ with $N$.

Hint 2

Parsing and checking the exact number of zeros can be done by scanning the input while maintaining counters of $O(\log N)$ bits.

Full solution

On input $w$ of length $N$, require exactly one delimiter $\#$, obtaining a candidate prefix $x$ and suffix of zeros. Reject if the form is wrong. Compute $|x|^k$ and verify that the suffix length is exactly $2^{|x|^k}$; this can be done in time polynomial in $N$ by scanning and binary counting.

If well formed, simulate the decider for $L$ on $x$. Its runtime is

because that many padding zeros occur in $w$. Parsing plus simulation is polynomial in $N$, so $L_{\mathrm{pad}}\in\mathrm P$.

Checkpoint

Padding does not make the original computation intrinsically faster; it enlarges the length against which runtime is measured.

Provenance note

Original exercise based on the standard padding technique; no student submission is an authority.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• Merged summary, pp. 124-130
• 2026 transcript 6
• Arora-Barak draft, padding discussion
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: Padding argument