# zbMATH — the first resource for mathematics

p-projection reducibility and the complexity classes $${\mathcal L}$$ nonuniform and $${\mathcal N}{\mathcal L}$$ (nonuniform). (English) Zbl 0611.03021
Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 527-535 (1986).
[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. A. K. Chandra, L. Stockmeyer and 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)$$.
Reviewer: A.Brandstädt

##### MSC:
 03D15 Complexity of computation (including implicit computational complexity) 68Q25 Analysis of algorithms and problem complexity