# If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets [closed]

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}|| 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?

• 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. – Joshua Grochow Dec 3 '20 at 16:54