<p>I am reading &quot;The Complexity Companion&quot; by Hemaspaandra &amp; Ogihara, I have a question about lemma 1.21.
In its proof, they suppose <span class="math-container">$L$</span> is some sparse language  in <span class="math-container">$\sf{NP}$</span> (<span class="math-container">$||L^{=n}||&lt;p(n)$</span> for some polynomial) and then construct the language
<span class="math-container">\begin{align*}
L' = &amp;\{0 \# n \# k , \text{ there are more than $k$ words of length $n$ in $L$}  \} \cup \\
&amp;\{ 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*}</span>
Since <span class="math-container">$L$</span> is in <span class="math-container">$\sf{NP}$</span>, then <span class="math-container">$L'$</span> is <span class="math-container">$\sf{NE}$</span>. Then, one can construct a <span class="math-container">$\sf{P}$</span> algorithm for <span class="math-container">$L$</span> by checking in <span class="math-container">$L'$</span> each of the words <span class="math-container">$0 \# n \# 0, \dots , 0 \# n \# p(n)$</span> in order to obtain <span class="math-container">$c=||L^{=n}||$</span>, and then checking if <span class="math-container">$1\#n\#c \#i \#j \in L'$</span> for <span class="math-container">$i \in \{1,\dots,c\} , j \in \{1,\dots,n\}$</span>, this is a polynomial number of checks in <span class="math-container">$L'$</span>, so (a priori) one would get that <span class="math-container">$L \in E$</span>. But they claim that even though <span class="math-container">$L'$</span> is <span class="math-container">$NE$</span>, its individual running time in this case is <strong>actually</strong> <span class="math-container">$O(\log n)$</span> which of course solves this problem.</p>
<p>Why is this? Is it because of the size of the input is made smaller when coded in binary?</p>

CC BY-SA 4.0
2020-12-03T16:54:46.800Z
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
CC BY-SA 4.0
2020-12-04T12:24:25.603Z
Please convert it to an answer.
Mohammad Al-Turkistany
<cc.complexity-theory><exp-time-algorithms>
If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets
omega-stable
# If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets

(Asked by: username_0 on 2020-12-03)

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?

**Tags:** cc.complexity-theory, exp-time-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: Please convert it to an answer.  

---

## 0 answers

