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.


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?

  • $\begingroup$ You can easily simulate these by usual {And, Or, Not} circuits plus random bits. $\endgroup$ – Kaveh Jan 13 '13 at 7:46
  • $\begingroup$ How do you define the (bounded-error) recognition of a Boolean function by a 2pfa? $\endgroup$ – Abuzer Yakaryilmaz Jan 13 '13 at 8:01
  • $\begingroup$ @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. $\endgroup$ – kbkb Jan 13 '13 at 8:48
  • 1
    $\begingroup$ @KasparsBalodis: Do you have a 2pfa for each $ f $ and $ n $, i.e. $ P_{n}^f $? $\endgroup$ – Abuzer Yakaryilmaz Jan 13 '13 at 9:46
  • 1
    $\begingroup$ @AbuzerYakaryilmaz: Yes. I updated the question to clarify it more formally. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – kbkb Jan 16 '13 at 12:19
  • $\begingroup$ Yes I believe you misunderstand. After fixing the randomness there is no randomness left. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 16 '13 at 12:55
  • $\begingroup$ 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. $\endgroup$ – kbkb Jan 21 '13 at 9:53
  • $\begingroup$ 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. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 21 '13 at 12:07
  • $\begingroup$ 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. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 21 '13 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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