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
0.95602906
0 references
0.94825715
0 references
0.9254713
0 references
0.91057324
0 references
0.90910465
0 references
0.90910465
0 references
0.90803474
0 references
0.90414405
0 references
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