The critical complexity of graph properties
type: Item
instance of: scholarly article
title: The critical complexity of graph properties
zbMATH Open document ID: 0542.68026
DOI: 10.1016/0020-0190(84)90019-X
author: Gy. Turán
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: The critical complexity of a Boolean function \(f(x_ 1,...,x_ n)\) is \(c(f):=\max \{| \{i:\quad f(x)\neq f(x^ i)\}|:\quad x\in \{0,1\}^ n\},\) where \(x^ i\) is obtained by changing the i-th component of x. \textit{S. Cook} and \textit{C. Dwork} [Bounds on the time for parallel RAMs to compute simple functions, Proc. 14th ACM STOC, 231-233 (1982)] proved that log c(f) (in base \({1\over2}(5+\sqrt{21}))\) is a lower bound to the time needed by a parallel RAM to compute f. \textit{H.-U. Simon} [Lect. Notes Comput. Sci. 158, 439-444 (1983; Zbl 0523.68036)] gave a sharp \(\Omega\) (log n) bound for the critical complexity of nondegenerate Boolean functions. Here it is shown that if \(n=\left( \begin{matrix} m\\ 2\end{matrix} \right)\) and f is a nontrivial property of graphs on m vertices, then \(c(f)\geq \lfloor m/4\rfloor.\) (The property of containing an isolated point shows that the bound is sharp within a constant factor.) This implies an \(\Omega\) (log n) lower bound to the parallel complexity of graph properties.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3862431
zbMATH Keywords: parallel processing
zbMATH Keywords: critical complexity
zbMATH Keywords: Boolean function
zbMATH Keywords: parallel complexity of graph properties
MaRDI profile type: Publication
cites work: On recognizing graph properties from adjacency matrices
full work available at URL: 0020-0190(84)90019-x
OpenAlex ID: W2089621728
description: scientific article; zbMATH DE number 3862431