I was going thorough this paper: (P=BPP unless E has sub-exponential circuits: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf) and I am somewhat struggling with some basics from the paper that I quote below:

Definition 1: Let $m$ and $l$ be positive integers. Let $f:\{{0,1}\}^m→\{{0,1}\}^l$. $S(f)$, the worst-case circuit complexity of $f$, is the minimum number of gates for a circuit $C$ with $C(x)=f(x)$ for every $x∈\{{0,1}\}^m$.

2.2 Hardness versus Randomness: For this section only, we use $f,g,h$ to denote a Boolean function on strings of all lengths, and by $f_n,g_n,h_n$ their segments on n-bit strings. Also, let $E=DTIME(2^{O(n)})$.

Theorem 2: If there is a Boolean function $f∈E$ with $S(f_n )=2^{Ω(n)}$ then $P=BPP$.

Query 1: I am assuming the boolean function is given by its truth table of size $2^m.l$ with all possible entries. I am unclear what it means by this truth table (denoted by $f$) $f∈E/DTIME(2^{O(n)})$? How do you assign the truth table its runtime without having some circuit represent it? I am clear about the fact that $S(f)$ represents the size(i.e. the number of gates in) the smallest possible circuit that represents/calculates $f$.

Query 2: Can someone please explain and simplify the theorem ("if...then") part? I am clear about the complexity classes $P$ and $BPP$, but I am struggling with the condition?

  • $\begingroup$ A function maps binary strings (of arbitrary length) to binary strings. A Boolean function is the special case where the output is a single bit. The restriction of $f$ to inputs of length $n$ is denoted $f_n$. $\endgroup$ Nov 8, 2021 at 22:26
  • 1
    $\begingroup$ This paper is not a good starting point for complexity theory. I suggest starting with something simpler. $\endgroup$ Nov 8, 2021 at 22:27

1 Answer 1


The function $f$ is a Boolean function. It maps an input of arbitrary length to a single bit. Its signature is $$f\colon \{0,1\}^* \to \{0,1\}.$$ We denote its restriction to $n$-bit inputs by $f_n$, whose signature is $$f_n\colon \{0,1\}^n \to \{0,1\}.$$ For example, the parity function returns the parity of its inputs: $$ f(x_1,\ldots,x_m) = x_1 \oplus \cdots \oplus x_m, $$ where $m \geq 0$ is arbitrary. The restriction for inputs of length $n$ is $$ f_n(x_1,\ldots,x_n) = x_1 \oplus \cdots \oplus x_n. $$ Here the input length is fixed.

The main theorem states that P=BPP if there is some function $f$ such that

  1. There is a constant $C > 0$ and a Turing machine computing $f$ which runs in time $C2^{Cn}$ on inputs of length $n$.
  2. There is a constant $c > 0$ such that for all $n$, any circuit computing $f_n$ has size at least $c2^{cn}$.
  • $\begingroup$ So effectively (very crudely speaking as I understand) we have to demonstrate a sort of equivalence b/w the worst case runtime of a TM and circuit size of the equivalent minimum circuit for at least one exponential function? $\endgroup$
    – J.Doe
    Nov 9, 2021 at 9:31
  • $\begingroup$ Right. That’s a very believable claim, which is why we believe that P=BPP. $\endgroup$ Nov 9, 2021 at 10:28

Your Answer

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

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