Towards a complexity theory of synchronous parallel computation

zbMath0473.68041MaRDI QIDQ1158753

Stephen A. Cook

Publication date: 1981

Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)

zbMATH Keywords

alternating Turing machinesvector machinesparallel random access machinesconglomeratesuniform circuit families

Mathematics Subject Classification ID

Related Items (26)

An introduction to parallelism in combinatorial optimization ⋮ Fast parallel absolute irreducibility testing ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Parallel pointer machines ⋮ Array processing machines: an abstract model ⋮ On nondeterminism in parallel computation ⋮ Solving H-horizon, stationary Markov decision problems in time proportional to log (H) ⋮ A note on strategy elimination in bimatrix games ⋮ Parallel algorithms for solvable permutation groups ⋮ Parallel evaluation of arithmetic circuits ⋮ Complexity theory of parallel time and hardware ⋮ Graph layout problems ⋮ Weak parallel machines: A new class of physically feasible parallel machine models ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Finding optimal subgraphs by local search ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel models of computation: An introductory survey ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ 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 ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ Speedups of deterministic machines by synchronous parallel machines

This page was built for publication: Towards a complexity theory of synchronous parallel computation