# Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $\Theta \left( 2^n/n \right)$ (in fact almost all of them are such).

This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)

I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$. The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x_1, \ldots, x_n$ it outputs the correct result $f(x_1, \ldots, x_n)$ with probability $\geq 2/3$.

Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size? The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?

The question I actually am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.

Update:

More formally I want to prove the following:

There exists an infinite sequence of Boolean functions $f_1, f_2, \ldots$ of $n_1, n_2, \ldots$ ($n_1 < n_2 < \ldots$) variables such that for every sequence of 2pfas $P_{f_1}, P_{f_2}, \ldots$ such that $P_{f_i}$ recognizes $f_i$ with 2-sided bounded error (that is for every word $x_1, \ldots, x_{n_i}$ accepts it with probability $\leq \frac{1}{3}$ if $f_i(x_1, \ldots, x_{n_i}) =0$ and probability $\geq \frac{2}{3}$ if $f_i(x_1, \ldots, x_{n_i})=1$) the number of states grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of states $\left| P_{f_i} \right| > p(n_i)$.

If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?

• You can easily simulate these by usual {And, Or, Not} circuits plus random bits. – Kaveh Jan 13 '13 at 7:46
• How do you define the (bounded-error) recognition of a Boolean function by a 2pfa? – Abuzer Yakaryilmaz Jan 13 '13 at 8:01
• @Kaveh Yes, but the simulating circuit won't be of a polynomial size. To simulate 1 gate with a complex probability distribution you will have to have many random bits. – kbkb Jan 13 '13 at 8:48
• @KasparsBalodis: Do you have a 2pfa for each $f$ and $n$, i.e. $P_{n}^f$? – Abuzer Yakaryilmaz Jan 13 '13 at 9:46
• @AbuzerYakaryilmaz: Yes. I updated the question to clarify it more formally. – kbkb Jan 13 '13 at 11:04

You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.
• I am not sure if I completely understand your answer. I think there is a problem that (for 2pfa-s) I measure the device size $S$ by the number of states, but it doesn't imply any bound on how many bits do I need to describe the probabilistic transition function. And I don't see how can you determinize the transition function without a blowup in the number of states as each transition can be used many times during one run of the automaton. – kbkb Jan 16 '13 at 12:19