Oracle branching programs and Logspace versus \(P^*\)
The authors investigate the space complexity of the \(P\)- complete \(GEN\) problem by means of so-called oracle branching programs. \(GEN\) consists of determining membership in a subalgebra of a general (not necessarily associative) binary algebra (input as a multiplication table). natural subclasses of \(P\) can be expressed as natural subproblems for \(GEN\). Finally, the authors prove optimal lower bounds on the size of oracle branching programs for \(GEN\) with certain natural oracles.
scientific article; zbMATH DE number 33434
scientific article