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 enter image description here as it appears in the book "Extremal combinatorics with applications to computer science 2ed."

  • $\begingroup$ @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. $\endgroup$
    – Jernej
    Jun 15, 2015 at 17:14
  • $\begingroup$ @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.$ $\endgroup$
    – Jernej
    Jun 15, 2015 at 17:25

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

  • $\begingroup$ 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)?$ $\endgroup$
    – Jernej
    Jun 15, 2015 at 19:33
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jun 15, 2015 at 22:47
  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Jun 16, 2015 at 7:57
  • $\begingroup$ OK, @Jernej, I've spelled everything out and solved the exercise. See the edited answer. $\endgroup$
    – D.W.
    Jun 16, 2015 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.