A doubt in Ladner's Proof

Question

I got stuck in Ladner's Proof while reading "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. Pardon me if I'm missing something really obvious here but the authors do the following:

For every function $H\colon\mathbb{N}\to\mathbb{N}$ define

$$SAT_H=\{\psi01^{n^{H(n)}}: \psi \in SAT \ and \ n=|\psi|\}$$

Now $H$ is defined as follows:

$H(n)$ is the smallest number $i<\log \log n$ such that for every $x\in\{0,1\}^*$ with $|x|\le \log n$, $M_i$ (TM encoded by binary representation of $i$) outputs $SAT_H (x)$ within $i|x|^i$ steps. If there is no such number $i$ then $H(n)=\log \log n$.

$M_i$ outputs $SAT_H (x)$ is equivalent to the statement that: The machine $M_i$ on an input $x$ outputs a 1 $\iff$ $x \in SAT_H$.

My question is: By definition of $SAT_H$, every string in it will have length exactly $n+1+n^{H(n)}$.

For every string $x\in\{0,1\}^*$ with $|x|\le \log n$, we note that $|x|<n+1+n^{H(n)}$. So there does not exist any string $x\in\{0,1\}^*$ with $|x|\le \log n$ and $x \in SAT_H$.

This would mean that the machine $M_i$ should trivially output 0 for every string $x\in\{0,1\}^*$ with $|x|\le \log n$. But then how would such an argument be used for a proof? Where exactly am I going wrong?

Answer 1

Every string in $SAT_H$ has length $m+1+m^{H(m)}$ for some $m$. In particular, there will be strings of length at most $\log n$ whenever $m+1+m^{H(m)} \leq \log n$. For some reason you insist that $m$ equal $n$. Perhaps you should consider the following equivalent definition of $SAT_H$: $$SAT_H = \{\psi01^{|\psi|^{H(|\psi|)}} : \psi \in SAT\}. $$ There is, however, a subtle point: the definition of $H(n)$ relies on the set $SAT_H$, whose definition in turn relies on the definition of $H(n)$ in what seems to be a circular fashion! However, if you work out the details you see that $H(n)$ relies on those parts of $SAT_H$ which depend on $H(m)$ for much smaller $m$. Indeed, we need to know the members of $SAT_H$ of size at most $\log n$. Each such member comes from a $\psi$ of size $m+1+m^{H(m)} \leq \log n$, and in particular $m \leq \log n$. So we only need to know the value of $H$ on the much smaller values up to $\log n$.