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?


1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.