In Harvard CS 221 Computational Complexity, Lecture 3, it introduced Branching Programs

A branching program is a DAG that has 1 start node and 2 output nodes with out-degree 0, labelled 0 and 1. Each non-output node is labeled with one of x1, x2, . . . , xn and each node has 2 outgoing edges labeled 0 and 1

For example

an example of branching programs

There is a derived defination of read-once BranchingPrograms

the read-once restriction, where a read-once BP reads each input value at most once in any computation path

My question: Obviously every Branching Programs can transform to read-once type, so what is the worth of non-read once Branching Programs?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.