No label defined (Q3974873)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 17548
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 17548

      Statements

      0 references
      0 references
      26 June 1992
      0 references
      lower bounds
      0 references
      [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.
      0 references

      Identifiers