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)\).

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 |