scientific article; zbMATH DE number 3987266
[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)\).
- scientific article; zbMATH DE number 4041256
- scientific article; zbMATH DE number 4209586
- scientific article; zbMATH DE number 3904572
- The power of nondeterminism in polynomial-size bounded-width branching programs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- The power of nondeterminism in polynomial-size bounded-width branching programs
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- A survey of space complexity
- scientific article; zbMATH DE number 4209586 (Why is no real title available?)
- Gradually intractable problems and nondeterministic log-space lower bounds
- scientific article; zbMATH DE number 3976381 (Why is no real title available?)
- scientific article; zbMATH DE number 4085027 (Why is no real title available?)
- scientific article; zbMATH DE number 8782 (Why is no real title available?)
- scientific article; zbMATH DE number 17815 (Why is no real title available?)
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Lower bounds for the modular communication complexity of various graph accessibility problems
- \textsc{ReachFewL} = \textsc{ReachUL}
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
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 Q3751569)