No label defined (Q4036171)

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 168429
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 168429

      Statements

      16 May 1993
      0 references
      non-trivial, monotone graph property
      0 references
      randomized complexity
      0 references
      lower bound
      0 references
      isomorphism properties
      0 references
      Let \(C^ R(P)\) be the number of questions of the form `Does the graph \(G\) contain the edge \(e(i,j)\)?' that have to be asked in the worst case by any randomized decision tree algorithm for computing an \(n\)-vertex graph property \(P\). For non-trivial, monotone graph properties it is known that the deterministic complexity is \(\Omega(n^ 2)\) [see \textit{R. Rivest} and \textit{Vuillemin} , On recognizing graph properties from adjacency matrices, Theor. Comp. Sci. 3, 371-384 (1976; Zbl 0358.68079)]. The best uniform lower bound for all non-trivial, monotone graph properties is \(\Omega(n^{4/3})\) due to \textit{P. Hajnal} [Complexity of graph properties, An \(\Omega(n^{4/3})\) lower bound on the randomized complexity of graph properties. Combinatorica 11(2), 131-143 (1991; Zbl 0743.68076)]. No non-trivial, monotone graph property is known having a randomized complexity of less than \(n^ 2/4\). Some properties have been proven to have complexity of \(\Omega(n^ 2)\) [see \textit{A. Yao}, Probabilistic computation: towards a unified measure of complexity, Proc. 18th IEEE FOCS, 222-227 (1977)]. We refine the idea of Yao. This leads to a further improvement in the reductions of arbitrary graph properties to bipartite graph properties [see \textit{V. King}, Lower bounds on the complexity of graph properties, Proc. 20th ACM STOC, 468-476 (1988)] and yields a uniform lower bound for the subgraph isomorphism properties of \(\Omega(n^{3/2})\). Furthermore we show, that a large variety of isomorphism properties has as well as \(k\)-colourability require \(\Omega(n^ 2)\) questions.
      0 references

      Identifiers