Towards a complexity theory of synchronous parallel computation
From MaRDI portal
Publication:1158753
zbMath0473.68041MaRDI QIDQ1158753
Publication date: 1981
Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)
alternating Turing machines; vector machines; parallel random access machines; conglomerates; uniform circuit families
68Q25: Analysis of algorithms and problem complexity
Related Items
The complexity of computing the number of strings of given length in context-free languages, Oracle branching programs and Logspace versus \(P^*\), Expected parallel time and sequential space complexity of graph and digraph problems, Efficient algorithms for parallel sorting on mesh multicomputers, Parallel evaluation of arithmetic circuits, Finding optimal subgraphs by local search, Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms., Data independence of read, write, and control structures in PRAM computations, Parallel pointer machines