On oblivious branching programs of linear length. (English) Zbl 0756.68042

Krause, Matthias; Waack, Stephan

Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 287-296 (1989).

[For the entire collection see Zbl 0726.00019.]
We consider problems belonging to \(\mathbb{L}\). The results are the following.
(i) We prove exponential lower bounds for the graph accessibility problems \(GAP\), and \(GAP1\), and for the word problem of the free group of finite rank.
(ii) We prove the following results: — \({\mathcal P}_{DG1}\) is not contained in \(TISP_ \sigma(n,\log n)\). The sequence equality function \(Q_{2n}\) for which an exponential lower bound on input oblivious decision graphs was proved in N. Alon and W. Maas [Meanders, Ramsey theory and lower bounds for branching programs, Proc. 27th IEEE- FOCS, 410-417 (1986)] belongs to \({\mathcal P}_{DG1}\).
— \(TISP_ \sigma(n,\log n)\) is not contained in \({\mathcal P}_{DG1}\). \((HALFCLIQUE_ n)_{n\in\mathbb{N}}\) which belongs to
\(TISP_ \sigma(n,\log n)\), is not in \({\mathcal P}_{DG1}\) [S. Zak, Lect. Notes Comput. Sci. 176, 562-566 (1984; Zbl 0558.68044)].
— The union of \({\mathcal P}_{DG1}\) and \(TISP_ \sigma(n,\log n)\) is properly contained in \({\mathcal L}\).
The word problem of the free group for which there are exponential lower bounds for both models [see K. Kriegel and S. Waack, Inf. Theor. Appl. 22, No. 4, 447-459 (1988; Zbl 0664.68046)] belongs to \(\mathbb{L}\). This result suggests that current techniques don’t suffice to separate \(\mathbb{L}\) from larger complexity classes.

MSC:

68Q15

Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

lower bounds

Citations:

Zbl 0726.00019; Zbl 0558.68044; Zbl 0664.68046