Question: Prove that for any polynomial $p(n)$, there exist boolean functions that cannot be written down using a propositional formula of size at most $p(n)$
These are the steps I have taken so far:
- For n inputs (n>=1), there are $2^{2^n}$ boolean functions.
- For any polynomial p(n), there are at most $(n+3)^{p(n)}$ propositional formulae (as each symbol in the formula must be one of x1,...,xn, AND, OR, NOT
- $(n+3)^{p(n)} = 2^{log(n+3).p(n)} = O(2^{2^n})$ and thus $2^{log(n+3).p(n)} <= c.2^{2^n}$ for n >= n0 and some c
The main difficulty I'm finding here is showing that there exist n such that $2^{log(n+3).p(n)} < 2^{2^n}$, unless of course I've made some other mistake in the process. Does anyone know how I can finish off this proof? (My foundations in Maths aren't that great also by the way, so I may need a little bit more explaining if possible). Any help would be much appreciated!
It is easy to check that $\log (n + 3) \in \operatorname{O}(n+3)$, hence $(n + 3)^{p(n)} \in \operatorname{O}(2^{P(n)})$ with $P := (n + 3) \cdot p$.
A well known fact about the exponential function is that for any polynomial function $f$, $f(n) \in \operatorname{O}(2^n)$, in particular $P(n) \in \operatorname{O}(2^n)$. Hence, $\boxed{2^{P(n)} \in \operatorname{O}(2^{2^n})}$.