Computational Complexity HT25, Padding arguments

We apply a padding argument. The inclusion $\mathsf{EXP} \subseteq \mathsf{NEXP}$ is easy (deterministic time is a special case of nondeterministic time), so we aim to show that $\mathsf{NEXP} \subseteq \mathsf{EXP}$.

Take a language in $\mathsf{NEXP}$ and show the padded language is in $\mathsf P$:

Suppose $L \in \mathsf{NTIME}(2^{n^c})$ and an NTM $N$ decides it. Consider the language

\[L_\text{pad} = \lbrace \langle x, 1^{2^{|x|^c} } \rangle : x \in L\rbrace\]

Then $L _ \text{pad} \in \mathsf{P}$: Consider the NTM $N _ \text{pad}$ which given $y$, first checks if there is a string $z$ such that $y = \langle z, 1^{2^{ \vert z \vert ^c} } \rangle$ (possible in time $ \vert y \vert $). If not, output $0$. Otherwise, if $y$ is of this form, then simulate $M$ on $z$ for $2^{ \vert z \vert ^c}$ steps and output its answer. Then the running time is polynomial in $ \vert y \vert $, and so $L _ \text{pad} \in \mathsf{NP}$.

Then if $\mathsf P = \mathsf{NP}$, it follows that $L _ \text{pad}$ is in $\mathsf P$, and so is decided by some DTM $M _ \text{pad}$.

Show that $\mathsf{NEXP} \subseteq \mathsf{EXP}$ by using $N _ \text{pad}$:

If $L _ \text{pad}$ is in $\mathsf P$, then $L$ is $\mathsf{EXP}$: to determine whether an input $x$ is in $L$, we may pad the input and decide whether it is in $L _ \text{pad}$ by simulating the polynomial time machine $M _ \text{pad}$ on $x$. Padding the input to length $2^{ \vert x \vert ^c}$ can certainly be done in $\mathsf{EXP}$ time.

@example~ @sheets~

We may assume without loss of generality that all languages are over the alphabet $\Sigma = \lbrace 0, 1\rbrace$.

Take a language in $\mathsf{DTIME}(T(2^n))$ and show the padded language is in $\mathsf{DSPACE}(S(n))$:

Let $M$ be a DTM deciding $L$ in time $T(2^n)$.

Consider a language defined as follows:

\[L_\text{pad} = \lbrace x 0 1^{2^{|x|} - |x| - 1} \mid x \in L \rbrace\]

Then $L _ \text{pad} \in \mathsf{DTIME}(T(m))$, since it can be recognised by the following deterministic TM $M _ \text{pad}$:

• On input $y$ of length $m$:
  • Check that $y$ is of the valid form, reject otherwise (this can be done in time $m$)
  • If $y$ is of the correct form, $M’$ simulates $M$ on $x$, accepting iff $M$ accepts

Since $M$ halts in time $O(T(2^{ \vert x \vert }))$, $M _ \text{pad}$ halts in time $O(T(m)) + O(m) = O(T(m))$ since $m = 2^{ \vert x \vert }$ and $T(m) = \Omega(m)$.

Therefore by assumption, $L _ \text{pad} \in \mathsf{DSPACE}(S(m))$ and hence there is a machine $N _ \text{pad}$ deciding $L _ \text{pad}$ in $O(S(m))$ space.

Show that $\mathsf{DTIME}(T(2^n)) \subseteq \mathsf{DSPACE}(S(2^n))$ using $N _ \text{pad}$:

Now we may define a TM $N$ which decides $L$ in space $O(S(2^n))$:

• On input $x$
  • $N$ pads $x$ to $y = x 01^{2^{ \vert x \vert } - \vert x \vert - 1}$
  • $N$ simulates $N _ \text{pad}$ on $y$ and accepts iff $N _ \text{pad}$ accepts

We must verify that this can be done in space $O(S(2^n))$. Since $S = \Omega(\log n)$, it might be the case that we cannot store all of $y$ on a tape of $N$.

Instead of storing $y$ explicitly, $N$ maintains a pointer $i$ to the input tape of $N _ \text{pad}$.

• If $N _ \text{pad}$ is reading from the first $ \vert x \vert $ bits of input, $N$ reads the corresponding bit of its input tape.
• $i = \vert x \vert + 1$, $N$ knows that the corresponding symbol $N _ \text{pad}$ is “$0$”.
• If $ \vert x \vert +1 \le i \le 2^{ \vert x \vert }$, $N$ knows the corresponding symbol on the input tape of $N _ \text{pad}$ is $1$
• If $i > 2^{ \vert x \vert }$, $N$ knows the corresponding symbol is the blank symbol.

$N$ increments or decrements the pointer depending on whether the input tape head of $N _ \text{pad}$ moves right or left.

The space taken by $N$ is the space taken by the simulation of $N _ \text{pad}$, plus the additional required to maintain the pointer.

• $N _ \text{pad}$ runs in $O(S(2^n))$ space
• The pointer takes space $O(n)$ to store

Since $S(2^n) = \Omega(n)$, the total space required is $O(S(2^n))$. Hence $N$ decides $L$ in space $S(2^n)$, as required.

@example~ @sheets~

Suppose for a contradiction that $\mathsf{DSPACE}(n) = \mathsf P$.

We aim to show that this implies $\mathsf{DSPACE}(n^2) = \mathsf P = \mathsf{DSPACE}(n)$, a contradiction to the space hierarchy theorem.

The inclusion $\mathsf P \subseteq \mathsf{DSPACE}(n^2)$ follows from $\mathsf{P} \subseteq \mathsf{DSPACE}(n) \subseteq \mathsf{DSPACE}(n^2)$.

The inclusion $\mathsf{DSPACE}(n^2) \subseteq \mathsf P$ follows from a padding argument.

---

Take a language in $L \in \mathsf{DSPACE}(n^2)$ and show the padded language is in $\mathsf P$:

Pick some language $L \in \mathsf{DSPACE}(n^2)$ with corresponding DTM $M$. Consider the language

\[L_\text{pad} := \lbrace \langle x, 1^{|x|^2 - |x|} \rangle \mid x \in L \rbrace\]

Then $L _ \text{pad} \in \mathsf{DSPACE}(n)$, since it can be recognised by the following linear space TM $M _ \text{pad}$:

• On input $y$ of length $m$:
  • Check that $y$ is of the valid form, reject otherwise (this can be done in time $m$)
  • If $y$ is of the correct form, $M _ \text{pad}$ simulates $M$ on $x$, accepting iff $M$ accepts

Then $M _ \text{pad}$ halts in space $O(n^2) = O(m)$ for inputs of length $m$, and hence $L _ \text{pad} \in \mathsf{DSPACE}(n)$. But $\mathsf{DSPACE}(n) = \mathsf P$ by assumption.

---

Show that $\mathsf{DSPACE}(n^2) \subseteq \mathsf P$ using $M _ \text{pad}$:

But then we may decide $L \in \mathsf P$ using the following TM $N$:

• On input $x$:
  • Pad $x$ to $y = \langle x, 1^{ \vert x \vert ^2 - x} \rangle$
  • Simulate $M’$ on $y$
  • Accept iff $M’$ accepts

Then since $M _ \text{pad}$ runs in polynomial time and the padding only takes time $O(n^2)$, $L \in \mathsf{DSPACE}(n^2)$. Hence $\mathsf{DSPACE}(n^2) \subseteq \mathsf P$.

---

Then $\mathsf{DSPACE}(n^2) = \mathsf P = \mathsf{DSPACE}(n)$. But $\mathsf{DSPACE}(n^2) \ne \mathsf{DSPACE}(n)$ by the space hierarchy theorem.

@example~ @sheets~

This is a little more involved than the other padding arguments. Assume for a contradiction that

\[\mathsf{NSPACE}(n) = \mathsf{NSPACE}(n^{1.1})\]

The strategy is to first show the more general statement that

\[\mathsf{NSPACE}(n^{1.1}) \subseteq \mathsf{NSPACE}(n)\]

implies

\[\mathsf{NSPACE}(f(n)^{1.1}) \subseteq \mathsf{NSPACE}(f(n))\]

where $f(n)$ is space constructible.

By taking $f(n) = n^{1.1}$, this shows inductively that

\[\mathsf{NSPACE}(n^{1.1^k}) \subseteq \mathsf{NSPACE}(n)\]

for every $k \ge 1$. From this we may take $k$ large enough that $1.1^k \ge 3$. Then we have the following chain of inclusions

\[\mathsf{DSPACE}(n^3) \stackrel{\text{triv.} }\subseteq \mathsf{NSPACE}(n^3) \stackrel{\text{by above} }\subseteq \mathsf{NSPACE}(n) \stackrel{\text{Savitch} }\subseteq \mathsf{DSPACE}(n^2)\]

which contradicts the space hierarchy theorem.

---

Proof $\mathsf{NSPACE}(n^{1.1}) \subseteq \mathsf{NSPACE}(n)$ implies $\mathsf{NSPACE}(f(n)^{1.1}) \subseteq \mathsf{NSPACE}(f(n))$:

Take a language in $L \in \mathsf{NSPACE}(f(n)^{1.1})$ and show the padded language is in $\mathsf{NSPACE}(n)$:

Pick some $L \in \mathsf{NSPACE}(f(n)^{1.1})$ with NTM $N$. Let

\[L_\text{pad} = \lbrace x 01^{f(|x|) - |x| - 1} \mid x \in L\rbrace\]

Then $L _ \text{pad} \in \mathsf{NSPACE}(n)$, since we may consider the NTM $N _ \text{pad}$:

• On input $y$ of length $m$:
  • Checks if $y = x 0 1^{f( \vert x \vert ) - \vert x \vert - 1}$ for some $x$, rejects otherwise
  • Simulates $N$ on $x$, accepts iff it accepts

The check can be done in $\mathsf{NSPACE}(m^{1.1})$ since:

• $f(n)$ is space-constructible, so we may guess $\ell = \vert x \vert $ in $O(\log m)$ space, compute $f(\ell)$ in $O(f(\ell)) = O(m)$ space
• Simulating $N$ on $x$ takes time $O(f( \vert x \vert )^{1.1}) = O(m^{1.1})$

Hence by the assumption there is an NTM $M _ \text{pad}$ which decides $L _ \text{pad}$ in $\mathsf{NSPACE}(n)$.

This implies $L \in \mathsf{NSPACE}(f(n))$:

Consider the NTM $M$ which:

• On input $x$
  • Pads $x$ to $y = x 0 1^{f( \vert x \vert ) - \vert x \vert - 1}$
  • Simulates $N _ \text{pad}$ on $y$, accepts iff $N _ \text{pad}$ accepts

This can be done in space $f(n)$, since:

• Padding $x$ takes space $f( \vert x \vert )$, since $f(n)$ is space constructible.
• Simulating $M _ \text{pad}$ on $y$ takes space $O(f(n))$.

Hence $L \in \mathsf{NSPACE}(f(n))$, as required.

@example~ @sheets~