<p>I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with <a href="http://minicomplexity.org/machr.php?id=45" rel="nofollow noreferrer">two-way finite automata</a> and I will measure the complexity of a Boolean function by the number of states for the minimal automaton computing this function.<br>
Automaton $A$ computes $f$ if it recognizes the language $L_f=\left\{ x \in \{ 0, 1 \} ^n | f(x)=1 \right\}$.</p>

<p>The result that I want to get is that there exist hard Boolean functions - requiring superpolynomial number of states for any <em>probabilistic</em> (with arbitrary rational probabilities) two-way automaton that computes the function.</p>

<p>This result can be proven for <strong><em>deterministic</em></strong> automata:  </p>

<p><strong>Theorem.</strong> There exists an infinite sequence of Boolean functions $f_1, f_2, \ldots$ of $n_1, n_2, \ldots$ ($n_1 &lt; n_2 &lt; \ldots$) variables such that for every sequence of 2DFAs $A_{f_1}, A_{f_2}, \ldots$ such that $A_{f_i}$ computes $f_i$ the number of states grows superpolynomially - for every polynomial $p$ there exists $i$ such that the number of states $\left| P_{f_i} \right| &gt; p(n_i)$.</p>

<blockquote>
  <p><strong>Sketch of proof.</strong> We will use counting argument.<br>
  The alphabet including the endmarkers is $\Sigma = \left\{ 0, 1, \vdash, \dashv \right\}$.<br>
  The number of determinstic two-way automata with $k$ states is no more than $(3 \cdot k)^{ \left| \Sigma \right| \cdot k } = 2^{4 \cdot k \cdot \log_{2}{3k} }$ - for every state and every symbol (hence the $\left| \Sigma \right| \cdot k$ part) there is a transition to some state and the transition itself can be one of 3 types - moving the head left, right or not moving (hence the $(3 \cdot k)$ part).<br>
  The number of Boolean functions on $n$ variables is $2^{2^n}$.<br>
  If $k = p(n)$ then the number of automata is no more than $2^{p'(n)}$ (where $p(n)$ and $p'(n)$ are polynomials) which is less than $2^{2^n}$ therefore there are more Boolean functions than automata of polynomial size. So there must be a Boolean function without a polynomial size automata $\blacksquare$</p>
</blockquote>

<p>This result can also be extended to <strong><em>nondeterministic</em></strong> automata.<br>
The number of 2NFAs with $k$ states is no more than $ 2^{3 \cdot k \cdot k \cdot \left| \Sigma \right|} = 2^{12 \cdot k^2}$ (because every transition from a state to a state with a given symbol and head movement can either be there or not be) which for $k$ polynomialy related to $n$ is still $2^{p(n)}$.</p>

<p>Now let's consider <strong><em>probabilistic</em></strong> automata. That is, for each transition from a state to a state with given input symbol and head movement there is a probability from a set $S \subseteq [0,1]$ assigned to it. Of course the probabilities for all transitions from a given state and input symbol must sum to 1. We will consider bounded-error computation - the automaton has to give the correct answer with probability $\geq \frac{2}{3}$.</p>

<p>If $S = \left\{ 0, \frac{1}{2}, 1 \right\}$ (these are sometimes called coin-flipping automata) then the result still holds - there are no more than $3^{3 \cdot k^2 \cdot \left| \Sigma \right|} = 2^{12 \cdot \log_{2}{3} \cdot k^2}$ such automata.</p>

<p>The result also holds for any other set $S$ ($S$ is allowed to depend on $n$) that is considerably smaller than $2^{2^n}$. The number of such automata is no more than $\left| S \right|^{12 \cdot k^2}$. For example $\left| S \right| = 2^{1.99^n}$ would be fine.</p>

<p><strong>The question:</strong> What happens if we allow all rational probabilities? Does there exist a hard Boolean function for such probabilistic two-way automata?<br>
Intuitively, going from probabilities from a quite large set $S$ to arbitrary rational probabilities shouldn't make a big difference, however the problem is that this counting argument doesn't work anymore.</p>

<p>This question for logical circuits was answered <a href="https://cstheory.stackexchange.com/questions/15065/probabilistic-circuit-complexity-or-size-of-probabilistic-2-way-automata-for-boo">here</a> (and the proof also extends to automata that works polynomial time, but not if the working time is unbounded).</p>

CC BY-SA 3.0
2013-03-13T09:55:12.387Z
Can you prove a lower bound for a specific, explicitly specified function?
András Salamon
CC BY-SA 3.0
2013-03-13T21:11:14.057Z
No. However I haven't much thought about specifying an explicit function. I think that could be hard similarly to circuit lower bounds for an explicit function.
kbkb
<cc.complexity-theory><automata-theory><lower-bounds><randomness><probabilistic-automata>
Size complexity of probabilistic two-way automata for a Boolean function
kbkb
# Size complexity of probabilistic two-way automata for a Boolean function

(Asked by: username_0 on 2013-03-10)

I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with [two-way finite automata](http://minicomplexity.org/machr.php?id=45) and I will measure the complexity of a Boolean function by the number of states for the minimal automaton computing this function.  
Automaton $A$ computes $f$ if it recognizes the language $L\_f=\left\{ x \in \{ 0, 1 \} ^n | f(x)=1 \right\}$.

The result that I want to get is that there exist hard Boolean functions - requiring superpolynomial number of states for any *probabilistic* (with arbitrary rational probabilities) two-way automaton that computes the function.

This result can be proven for ***deterministic*** automata:

**Theorem.** 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 2DFAs $A\_{f\_1}, A\_{f\_2}, \ldots$ such that $A\_{f\_i}$ computes $f\_i$ the number of states grows superpolynomially - for every polynomial $p$ there exists $i$ such that the number of states $\left| P\_{f\_i} \right| > p(n\_i)$.

> **Sketch of proof.** We will use counting argument.  
> The alphabet including the endmarkers is $\Sigma = \left\{ 0, 1, \vdash, \dashv \right\}$.  
> The number of determinstic two-way automata with $k$ states is no more than $(3 \cdot k)^{ \left| \Sigma \right| \cdot k } = 2^{4 \cdot k \cdot \log\_{2}{3k} }$ - for every state and every symbol (hence the $\left| \Sigma \right| \cdot k$ part) there is a transition to some state and the transition itself can be one of 3 types - moving the head left, right or not moving (hence the $(3 \cdot k)$ part).  
> The number of Boolean functions on $n$ variables is $2^{2^n}$.  
> If $k = p(n)$ then the number of automata is no more than $2^{p'(n)}$ (where $p(n)$ and $p'(n)$ are polynomials) which is less than $2^{2^n}$ therefore there are more Boolean functions than automata of polynomial size. So there must be a Boolean function without a polynomial size automata $\blacksquare$

This result can also be extended to ***nondeterministic*** automata.  
The number of 2NFAs with $k$ states is no more than $ 2^{3 \cdot k \cdot k \cdot \left| \Sigma \right|} = 2^{12 \cdot k^2}$ (because every transition from a state to a state with a given symbol and head movement can either be there or not be) which for $k$ polynomialy related to $n$ is still $2^{p(n)}$.

Now let's consider ***probabilistic*** automata. That is, for each transition from a state to a state with given input symbol and head movement there is a probability from a set $S \subseteq [0,1]$ assigned to it. Of course the probabilities for all transitions from a given state and input symbol must sum to 1. We will consider bounded-error computation - the automaton has to give the correct answer with probability $\geq \frac{2}{3}$.

If $S = \left\{ 0, \frac{1}{2}, 1 \right\}$ (these are sometimes called coin-flipping automata) then the result still holds - there are no more than $3^{3 \cdot k^2 \cdot \left| \Sigma \right|} = 2^{12 \cdot \log\_{2}{3} \cdot k^2}$ such automata.

The result also holds for any other set $S$ ($S$ is allowed to depend on $n$) that is considerably smaller than $2^{2^n}$. The number of such automata is no more than $\left| S \right|^{12 \cdot k^2}$. For example $\left| S \right| = 2^{1.99^n}$ would be fine.

**The question:** What happens if we allow all rational probabilities? Does there exist a hard Boolean function for such probabilistic two-way automata?  
Intuitively, going from probabilities from a quite large set $S$ to arbitrary rational probabilities shouldn't make a big difference, however the problem is that this counting argument doesn't work anymore.

This question for logical circuits was answered [here](https://cstheory.stackexchange.com/questions/15065/probabilistic-circuit-complexity-or-size-of-probabilistic-2-way-automata-for-boo) (and the proof also extends to automata that works polynomial time, but not if the working time is unbounded).

**Tags:** cc.complexity-theory, automata-theory, lower-bounds, randomness, probabilistic-automata
> **Comments:**
> **username_1**: Can you prove a lower bound for a specific, explicitly specified function?  
> **username_0**: No. However I haven't much thought about specifying an explicit function. I think that could be hard similarly to circuit lower bounds for an explicit function.  

---

## 0 answers

