跳到主要内容

分叉程序

阐述

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

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

EQROBP={B1,B2B1 and B2 are equivalent read-once branching programs }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 机

实例

性质

相关内容

参考文献