No label defined (Q3975161)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 17817
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 17817 |
Statements
26 June 1992
0 references
lower bounds
0 references
oracle branching programs
0 references
GEN
0 references
0.9490790963172911
0 references
0.7777665257453918
0 references
0.7709336876869202
0 references
0.7620095014572144
0 references
[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.
0 references