分叉程序

阐述

一个指定了起始节点的有向无环图，其中每个变量节点有两个出边分别标记了 0 和 1，两个出度为 0 的输出节点标为 0 和 1。这样的图计算了一个布尔函数。

如果每条路径上每个变量最多出现一次，则称它是一个一次读取的分叉程序。

E Q_{\mathrm{ROBP}}=\left\{\left\langle B_{1}, B_{2}\right\rangle \mid B_{1} \text { and } B_{2} \text { are equivalent read-once branching programs }\right\}

这个问题属于 BPP，参见概率 Turing 机。