I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21. In its proof, they suppose $L$ is some sparse language in $\sf{NP}$ ($||L^{=n}||<p(n)$ for some polynomial) and then construct the language \begin{align*} L' = &\{0 \# n \# k , \text{ there are more than $k$ words of length $n$ in $L$} \} \cup \\ &\{ 1\#n\#c \#i \#j \text{ there are $c$ words $z_1,\dots,z_c$ in $L$ of length $n$ such that the $j$-th bit of $z_i$ is 1 } \} \end{align*} Since $L$ is in $\sf{NP}$, then $L'$ is $\sf{NE}$. Then, one can construct a $\sf{P}$ algorithm for $L$ by checking in $L'$ each of the words $0 \# n \# 0, \dots , 0 \# n \# p(n)$ in order to obtain $c=||L^{=n}||$, and then checking if $1\#n\#c \#i \#j \in L'$ for $i \in \{1,\dots,c\} , j \in \{1,\dots,n\}$, this is a polynomial number of checks in $L'$, so (a priori) one would get that $L \in E$. But they claim that even though $L'$ is $NE$, its individual running time in this case is actually $O(\log n)$ which of course solves this problem.

Why is this? Is it because of the size of the input is made smaller when coded in binary?

  • 2
    $\begingroup$ Yes, the input size to the queries you are making to $L'$ is $O(\log n)$ because they are written in binary, so the fact that $L' \in \mathsf{E}$ means that those queries can each be answered in $2^{O(\log n)}=poly(n)$ time. $\endgroup$ – Joshua Grochow Dec 3 '20 at 16:54
  • $\begingroup$ Please convert it to an answer. $\endgroup$ – Mohammad Al-Turkistany Dec 4 '20 at 12:24