scientific article; zbMATH DE number 17548

From MaRDI portal
Publication:3974873





[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.











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)