Computing a boolean function with a small formula

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).$

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."

• @D.W. The theorem that the problem asks to use states what I've written above about the existence of the $n$-element set $S.$ I apologize for the inconvenience! My motivation was to write an as self-contained question as possible. – Jernej Jun 15 '15 at 17:14
• @D.W. As far as Adleman's statement goes one can find the exact statement in an eary (free) draft of the link thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/draft.pdf see page 249. And it can be confirmed from here that the $n$ is indeed the same for $S$ and $x.$ – Jernej Jun 15 '15 at 17:25

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.

• Thanks for writing such a detailed answer. Let me just try to clarify - isn't a good point for $a$ a value $y$ such that $F(a,y) = f(a)?$ – Jernej Jun 15 '15 at 19:33
• @Jernej, yes, that's much better (it leads to a cleaner application of Adleman's theorem). Thank you for the improvement. I've edited my answer. – D.W. Jun 15 '15 at 22:47
• I've given your answer ~10h of thought but I don't see how to construct the formula. As far as I can carry the hint is that if $F(a,y) = 1$ then $f(a) = 1$ since if $f(a) = 0$ then by definition $F(a,y) = 0$ But I don't see what happens if $F(a,y) = 0$ and how to encode all this as a formula of small size. Could you please expand the answer? – Jernej Jun 16 '15 at 7:57
• OK, @Jernej, I've spelled everything out and solved the exercise. See the edited answer. – D.W. Jun 16 '15 at 17:56