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.


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


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^k2^n)$ time (computing on each input costs $O(n^k)$ time 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 TM on input of size $n$ is

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

So the language decided by this TM 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 TM.

  • $\begingroup$ Why does the number of circuits of size $n^k$ is $2^{(n+n^k)^2}$? $\endgroup$ – galah92 Mar 20 '18 at 16:02
  • $\begingroup$ @xskxzr Hi, I've noticed that you edited the question to make the body more readable, which is good. However, please don't put MathJax in titles. I replaced the MathJax in the title with unicode and David Richerby made the title even better by giving a description in 'English'. Please try to keep this in mind for the future. Thanks! $\endgroup$ – Discrete lizard Mar 20 '18 at 16:30
  • $\begingroup$ @galah92 That's a mistake. Now fixed. $\endgroup$ – xskxzr Mar 20 '18 at 17:20
  • 1
    $\begingroup$ @Discretelizard Thanks, I'll keep it in mind. Now I added some explanations for the equation. $\endgroup$ – xskxzr Mar 20 '18 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.