Problem der Äquivalenz zweier ROBP
Einfache Sprache
Gegeben zwei ROBP so gezeigt werden ob sie die selbe Boolesche Funktion repräsentieren.
Problem der Äquivalenz zweier ROBP
$$\mathrm{EQ}_\mathrm{ROBP} = \{\langle B_1,B_2\rangle\mid B_1\text{ und } B_2 \text{ sind äquivalente read-once branching programs}\}$$