## Parallel complexity theory |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Designing a Parallel Machine Model | 21 |

Variants of the Model | 39 |

Copyright | |

9 other sections not shown

### Other editions - View all

### Common terms and phrases

alternating Turing machine arithmetic instruction-set asymptotic binary bitonic sorting bits Boolean bounded carries value CCLk cell cessor channel Chapter circuit-value problem communication register configuration constant multiple constant number construct Corollary cube-connected cycles cube-connected lines dedicated processors defined denote depth deterministic Turing machine edges expander graphs feasible network fi(log finite follows function gate Goldschlager graph hardware induction hypothesis input instruction integers interconnection pattern Lemma log-cost lower-bound MIMD minimal instruction-set nondeterministic Turing machine number of processors number of values output P-complete packet parallel computation thesis parallel machine model phase polynomial Proof recursive restricted restricted-access network result running-time satisfy the parallel Section 3.1 sequence sequential shared-memory location shared-memory machine shuffle-exchange SIMD sorting algorithm sorting network strangers subgraphs Suppose symbol tape Theorem time-bounded time-step tion tth step unbounded fan-in circuit uniform circuit unit-cost measure universal network variable vertex vertices word-size work-tape zero