# 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. –  Kaspars Balodis 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. –  Kaspars Balodis Jan 13 '13 at 11:04
show 1 more comment

## 1 Answer

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. –  Kaspars Balodis Jan 16 '13 at 12:19
Yes I believe you misunderstand. After fixing the randomness there is no randomness left. –  Kristoffer Arnsfelt Hansen Jan 16 '13 at 12:55
Now I see. This approach indeed works for circuits because every gate in a computation is used only once and you can fix it. However it does not translate to 2-way probabilistic finite automata easily because there every state (and therefore also the transition function) can be used many times in a single computation. –  Kaspars Balodis Jan 21 '13 at 9:53
I was indeed thinking about circuits, and I am not sure what to do with automata. I have changed my answer to avoid claiming too much. –  Kristoffer Arnsfelt Hansen Jan 21 '13 at 12:07
Actually, can you not make it work for automata in the following way: Since you care only about strings of length n, each state will be visited at most n times. Then in the "automata" obtained after fixing randomness, each state will have a list of n next-state transition functions. Each time a state is visited, the next unused transition function is used. –  Kristoffer Arnsfelt Hansen Jan 21 '13 at 14:50
show 1 more comment