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^{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.

| cite | improve this answer | |
  • $\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
  • $\begingroup$ Confused here. I thought it is an open question whether we can prove that all EXP has sub exponential circuits (which implies P != NP). This seems to imply that such a proof is impossible? $\endgroup$ – Vervious Aug 19 '19 at 17:47

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.