# Connection between formula size and time complexity

Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.

Is there a connection between time complexity of $P$ and degree of $f$ and number of monomials in $f$?

• You can encode every problem with arbitrarily large formulae. What are you really asking?
– Raphael
Dec 5 '14 at 11:50
• I think you also need to formalize a bit more carefully what you mean when you say that a problem $P$ is encoded by a formula $f$. Here's one possibility: $P$ takes as input $x$ and returns a single bit (it's a decision problem); we say that $f$ encodes $P$ if $f(x)$ is the correct output on input $x$. Here's another possibility: problem $P$ is, on input $x$, compute the output $y=P(x)$; $f$ encodes $P$ if for all $x$, $f(x,y)=1$ iff $y=P(x)$ [i.e., $f(x,P(x))=1$ and $f(x,y')=0$ for all $y' \ne P(x)$]. What did you have in mind?
– D.W.
Dec 5 '14 at 20:52