Back to Boolean Circuits
Back to notes

# The Easy Witness Lemma

50%

## Easy witness for NEXP

If $\NTIME[2^n]\subseteq\SIZE[s(n)]$, then there is a constant $t\in\N$ such that for every $L\in\NTIME[2^n]$ and $x\in L$, there exists a witness $w$ for $x$ such that there exists a circuit of size $s(s(n^t)^t)^t$ whose truth table is $w$.

When $s(n)$ is polynomial (resp. quasi-polynomial), then the size of the witness circuit is also polynomial (resp. quasi-polynomial). In the following, we sketch the proof of the theorem. For the simplicity of presentation, we consider the case where $s(n)=n^k$ for some $k\in\N$.

The high-level idea of the proof is using unconditional circuit lower bound to derive contradiction. By assuming there is no easy witness for $\NTIME[2^n]$, we then know that the witness itself is a hard function since it cannot be efficiently encoded by a small circuit. As a result, by feeding this hard function into the Nisan-Wigderson generator, we can then derandomize the Merlin-Arthur protocol for a hard language (who has unconditional circuit lower bound) into a nondeterministic time algorithm. By applying the assumption that $\NTIME[2^n]$ has a small circuit again, we get a contradiction and thus the witness can be encoded into a small circuit.

The above explanation is a little bit sketchy and we explain the proof in more details as follows.

### Unconditional circuit lower bound

Here, we are using the most naive unconditional circuit lower bound by diagonalization. That is, enumerating all the possible algorithms/machines and negate on one input length with each of them. Concretely, we have the following lemma.

For any $k\in\N$, there exists a language $L_{\text{hard}}\in\TIME[2^{n^{k+1}}]$ such that $L\not\in\SIZE[n^{O(k)}]$.

The proof is actually quite simple. It is easy to see that such language $L_{\text{hard}}$ exists in $\SPACE[n^{k+1}]$ as $\SIZE[n^{O(k)}]$ can be enumerated in $n^{k+1}$ space. The lemma then follows by $\SPACE[n^{k+1}]\subseteq\TIME[2^{n^{k+1}}]$.

As an important remark, note that this lower bound can be strengthen in the sense that there would be no size $n^{O(k)}$ circuit that computes $L_{\text{hard}}$ infinitely often.