Boolean Recurrence Equation (BRE)
Category: Algebra
Input
A four-tuple $(M, B, F, j)$, where $M$ is a $1 \times n$ Boolean vector, $B$ is an $n \times n$ Boolean matrix, $F$ is an $n \times 1$ Boolean vector, and $j$ is an integer in the range $0$ to $n$.
Problem
Is the first entry of $M * Y_j$ a 1? $Y_j$ is defined recursively as $Y_0 = F$, $Y_k = B \cdot Y_{k-1}$ for $k \geq 1$. $\overline{Y}$ denotes the complement of $Y$.
Status
$\P$-complete (Bertoni et al [1]).
Remarks
The reduction to show hardness is from an alternating Turing machine that uses $O(\log n)$ space.
If $0 \leq j \leq (\log n)^k$, then the problem is complete for $\mathsf{AC}^k$ [1]. That is, the class of problems accepted by alternating Turing machines in $O(\log n)$ space and $O((\log n)^k)$ alternations.