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

      0 references
      26 June 1992
      0 references
      lower bounds
      0 references
      oracle branching programs
      0 references
      GEN
      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

      Identifiers