scientific article; zbMATH DE number 17548
[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 \textit{N. Alon} and \textit{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}\) [\textit{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 \textit{K. Kriegel} and \textit{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.
- On oblivious branching programs of linear length
- scientific article; zbMATH DE number 827986
- scientific article; zbMATH DE number 4172378
- Efficient oblivious branching programs for threshold and mod functions
- The power of nondeterminism and randomness for oblivious branching programs
- On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
- scientific article; zbMATH DE number 706832
- On the power of randomized branching programs
- Stochastic Algorithms: Foundations and Applications
- scientific article; zbMATH DE number 3913677
- Oracle branching programs and Logspace versus \(P^*\)
- scientific article; zbMATH DE number 4213443 (Why is no real title available?)
- Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
- Tight Bounds on Oblivious Chaining
- Separating counting communication complexity classes
- On oblivious branching programs of linear length
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 Q3974873)