Can someone throw some light on how to create a branching program from a given function? I have followed the definition of $BP$ on wiki and here. But I could not find any way to convert a function to $BP$.

P.S: I know $BP$ can be of exponential size for some functions. So any simple function on 3-4 variables will do for example $PARITY$ or $MAJ$.

  • $\begingroup$ This site is for research-level question, which this is not. This would be a fine question for cs.stackexchange.com . $\endgroup$ – Emil Jeřábek Aug 7 '18 at 9:11
  • 1
    $\begingroup$ Ok thanks. I thought this is a good question for TCS. $\endgroup$ – chelsea Aug 7 '18 at 9:14

Even though I agree that this is not the right place to ask this question, you might want to look into the following book that contains everything about branching programs that you every wanted to know:

Ingo Wegener: Branching Programs and Binary Decision Diagrams. SIAM 2000, ISBN 0-89871-458-3


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.