Lies-einmal Binäres Entscheidungsdiagramm

Einfache Sprache

Def. Lies-einmal Binäres Entscheidungsdiagramm

Ein Lies-einmal Binäres Entscheidungsdiagramm (auch read-once branching program genannt) ist ein Binäres Entscheidungsdiagramm, wobei jede Variable höchstens ein mal abgefragt werden darf. Auf einem Weg in dem Diagramm darf jede Variable also nur einmal vorkommen.

Die Äquivalenz zweier read-once branching programs zu zeigen liegt in BPP nach dem Satz EQ-ROBP in BPP.