Computing a boolean function with a small formula

Question

Suppose that $x = (x_1,\ldots,x_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose $y = (y_1,\ldots,y_m)$ is a binary vector and that $F(x,y)$ is a binary formula of size $k.$ Here by size I mean the number of leaves in $F.$

Suppose I have vectors $S = \{s_1,\ldots,s_n\}$ such that for any $x \in \{0,1\}^n$ there is a $s \in S$ such that we have $$ F(x,s) = f(x).$$

I need to prove that in this case I can express $f(x)$ as a boolean formula of size $O(n\cdot k).$

What would be the idea about this?

Since for every input $x$ we have an $s \in S$ one could encode the specific $s$ for every one of the $2^n$ possible inputs but this would give a too large formula.

Edit. The original text as it appears in the book "Extremal combinatorics with applications to computer science 2ed."

Answer 1

Something has gone wrong in the way you applied Adleman's theorem: it has led you to try to prove something that isn't actually true.

The statement the book asks you to prove is true. There is a good deterministic algorithm for $f$. Adleman's theorem, applied properly, immediately gives you a good deterministic algorithm for $f$. Just make sure you pick the definition of "good point" correctly. Hint: A good point for $a$ is a value $y$ such that $F(a,y)=f(a)$. What can you conclude about $f(a)$, if you observe a point $y$ such that $F(a,y)=1$? Now an application of Adleman's theorem immediately leads to a simple deterministic algorithm for computing $f$ and a small boolean formula for $f$. In particular, we get the following boolean formula for $f$:

$$f(x) = F(x,s_1) \lor F(x,s_2) \lor \dots \lor F(x,s_n).$$

Why does this work? Well, if $f(x)=0$, then we're guaranteed that $F(x,y)=0$ for all $y$ (this comes directly from the exercise in your book), so in particular every term of the above disjunction is 0, so this formula gives the correct answer for $f(x)$. On the other hand, if $f(x)=1$, then Adleman's theorem guarantees that there exists at least one $s_i \in S$ that's a good point for $x$, i.e., at least one $s_i$ such that $F(x,s_i)=f(x)=1$, which means that the above disjunction is 1, so this formula gives the correct answer for $f(x)$ in this case, too.

In contrast, the claim you're trying to prove isn't true. Here's an explicit counterexample. Let $F(x,s)=s$ (so $m=1$), $s_0=0$, $s_1=1$ (so $S=\{0,1,\dots\}$), and let $f$ be any function with no small formula. Then it is easy to verify that for all $x$ there exists $s \in S$ such that $F(x,s)=f(x)$: in particular, you can take $s=f(x)$. Notice that we didn't use anything about $f$, so we were free to choose $f$ any way we want. It is also easy to see that $F$ has a small formula, for this choice of $F$. Therefore, this choice of $F,S,f$ satisfies all the preconditions of your claim. However, (by assumption) $f$ doesn't have a small formula, so this is a counterexample for your claim.

There's a crucial difference between "there exists at least one $s$ for which (blah) is true" vs "(blah) is true for a large fraction of $s$".

I don't know how you got to your claim or what went wrong in your translation from the book's exercise to your claim, but I suspect you didn't apply Adleman's theorem quite right, or the way you applied it didn't give you strong enough conclusions/assumptions about the properties that $F$ has.