Proving that EXP doesn't have polynomial-size circuits

Question

How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$?

I have a reminder that says $$ \mathrm{EXP} =\bigcup_{c\in\mathbb{N}} \mathrm{DTIME}\left(2^{n^c}\right). $$

Thought of building a TM that on input $x$ of size $n$, finds a function $f_{n}$ such that there is no circuit of size $n^k$ that calculates it. Go through all functions and for each one go through all the circuits and check whether they calculate the function. If none of them calculates it then it's what we want.

I don't know how to show this is $\mathrm{EXP}$ or how to prove this solves the problem.

Answer 1

You can consider a circuit as a directed graph where nodes are inputs and gates. For a circuit of size $n^k$ on input of size $n$, there are at most $(n+n^k)^2$ edges, and each node (gate) has three possibilities, so the number of such circuits is at most

$$3^{n^k}\cdot2^{\left(n+n^k\right)^2}=O\left(2^{n^{2k+2}}\right).$$

So you need only to enumerate at most $O\left(2^{n^{2k+2}}\right)$ functions. In addition, checking whether a circuit of size $n^k$ calculates a function costs $O(n^{2k}2^n)$ time since computing on each input costs $O(n^{2k})$ time (here we compute the running time under a RAM rather than a TM without loss of generality) and there are $2^n$ inputs. Note for each function, you need to go through all circuits, and for each circuit, you need to check whether it calculates the function, so the total running time of the RAM on input of size $n$ is

$$ O\left(2^{n^{2k+2}}\right)\cdot O\left(2^{n^{2k+2}}\right)\cdot O(n^{2k}2^n)=O\left(2^{n^{2k+4}}\right). $$

So the language decided by this RAM is in $\mathrm{EXP}$ (note $k$ is a fixed constant). Obviously no family of circuits of size $n^k$ decides this language by the construction of the RAM.