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?
A doubt in Ladner's Proof
complexity theory
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$.