Extending Branching Programs with Memory

Abstract

In this study, we continue the line of research that was initiated by Mengel [Men13] wherein he showed that by augmenting algebraic branching programs with a single stack as memory and randomaccess memory we obtain characterizations for the classes VP and VNP respectively. In this thesis, we introduce k-stack branching programs, a generalization of Mengel’s single-stack branching program, and show that when k ⩾ 2, the computational model characterizes the class VNP. Due to this, we get a clean characterization of the classes VBP, VP, and VNP using algebraic branching programs with 0, 1, and 2 stacks as memory. Similar to what happens with pushdown automata, we show that a branching program with 2 stacks as memory is equivalent to a branching program with a queue as memory. Next, we impose restrictions such as bounded stack height and bounded branching program width upon stack branching programs and show that any polynomial family in VP can be computed by a polynomial-sized stack branching program with the stack height bounded by O(log(n) 2 ). Finally, we detail a technique using which we can construct a (k + 1)-stack branching program that computes P ¯(e)∈{0,1}m−n qm(x1, · · · , xn, e¯) when given a k-stack branching program that computes qm(x1, · · · , xn, e¯). Using this we give an alternate proof for the fact that exponential summation of a polynomial family in VP gives a polynomial family in VNP which was originally shown in [Val82]. This technique combined with one of the previous result of adding more stacks to a 2-stack branching program does not increase the computational power gives us alternate proofs for • exponential summation of a polynomial family in VBP gives a polynomial family in VNP and • exponential summation of a polynomial family in VNP gives a polynomial family in VNP.