No label defined (Q3751569)

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 3987266
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3987266

      Statements

      0 references
      1986
      0 references
      nonuniform complexity classes
      0 references
      logarithmic space complexity
      0 references
      Turing machine
      0 references
      branching programs
      0 references
      graph accessibility problem
      0 references
      p-projection reducibility
      0 references
      [For the entire collection see Zbl 0596.00021.] Let \({\mathcal L}\) (\({\mathcal N}{\mathcal L})\) denote the class of languages \(L\subseteq \{0,1\}^*\) which can be accepted by deterministic (nondeterministic) Turing machines with a two-way read-only input tape and a log n space bounded work tape. Let \({\mathcal L}(nonuniform)\) (\({\mathcal N}{\mathcal L}(nonuniform))\) denote the class of languages \(L\subseteq \{0,1\}^*\) for which there is a polynomial p(n) and a log n space-bounded deterministic (nondeterministic) Turing machine M such that for all w with \(| w| =n\) there is an \(\alpha_ n\in \{0,1\}^*\) with \(| \alpha_ n| \leq p(n)\) such that M accepts \(w\square \alpha_ n\) iff \(w\in L\) (\(\square\) the blank symbol) \((\alpha_ n\) is called the advice, cf. \textit{A. K. Chandra}, \textit{L. Stockmeyer} and \textit{U. Vishkin}, SIAM J. Comput. 13, 423-439 (1984; Zbl 0538.68038)). Let \({\mathcal P}_{BP}\) denote the class of all problems \(F=\{f_ n\}\) for which the functions \(f_ n\) can be computed by branching programs of size polynomial in n (i.e. directed acyclic graphs with outdegrees 2 or 0 computing Boolean functions with a polynomial number of nodes of outdegree 2). Let \({\mathcal P}_{N_ 1BP}\) be the class of problems solvable by so-called 1-time-only-nondeterministic branching programs of polynomial size. Basing on an idea of Savitch the author gives the characterizations \({\mathcal P}_{BP}={\mathcal L}(nonuniform)\) and \({\mathcal P}_{N_ 1BP}={\mathcal N}{\mathcal L}(nonuniform).\) Furthermore it is shown that \(GAP^{(r)}\)- a restriction of the graph accessibility problem GAP to monotone graphs of outdegree 1 - is complete in \({\mathcal L}\) (nonuniform) with respect to the so-called p-projection reducibility introduced in the reference mentioned above (and also complete in \({\mathcal L}).\) Let \({\mathcal K}^*\) denote the closure of \({\mathcal K}\) under the p- projection reducibility. Then \({\mathcal L}^*={\mathcal L}(nonuniform)={\mathcal L}(nonuniform)^*\) and \({\mathcal N}{\mathcal L}^*={\mathcal N}{\mathcal L}(nonuniform)={\mathcal N}{\mathcal L}(nonuniform)^*\) hold. Since GAP is known to be complete in \({\mathcal N}{\mathcal L}\) as well as in \({\mathcal N}{\mathcal L}(nonuniform)\) with respect to p-projection reducibility one has the following corollary: GAP\(\leq \!/GAP^{(r)}\) iff \({\mathcal L}(nonuniform)\varsubsetneq {\mathcal N}{\mathcal L}(nonuniform)\).
      0 references

      Identifiers