scientific article; zbMATH DE number 17817
[For the entire collection see Zbl 0726.00018.] Oracle branching programs are defined and GEN subproblems complete for standard subclasses of \(P\) are exhibited, justifying the choice of GEN as a particular appropriate \(P\)-complete problem to study. We then examine specific ``natural oracle branching programs solving the GEN subproblem in which \(S=\{1\}\), denoted as \(\text{GEN}(\{1\})\). A result is the following: \(2^{n-2}\) is a matching upper and lower bound on the size of a branching program for \(\text{GEN}(\{1\})\) whose nodes can only specify \(T\subseteq\{1,2,\dots,n\}\) and branch \(n\) ways according to the least groupoid elements in \(\langle T\rangle\setminus T\) (with a branch labeled 0 corresponding to \(\langle T\rangle=T\)). Similar bounds are then obtained for more general ``natural oraces. Open problems are listed throughout the paper, the meaning of our results is discussed.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3975161)