Paper Info
Title
A complexity theory for unbounded fan-in parallelism
Abstract
A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed on the fan-in of gates. It is shown that these models can simulate one another with the number of processors preserved to within a polynomial and parallel time preserved to within a constant factor. Reducibilities that preserve the measure in this sense are defined and several reducibilities and equivalences among problems are given. New upper bounds on the (unbounded fan-in) circuit complexity of symmetric Boolean functions are proved.
Year
DOI
Venue
1982
10.1109/SFCS.1982.53
FOCS
Keywords
Field
DocType
parallel processing,polynomials,asynchronous transfer mode,boolean functions,logic gates,time measurement,upper bound,yttrium,sorting,circuits,computer simulation,computed tomography,registers,computational modeling,gold,radiation detectors,robustness,integrated circuits,switches,circuit complexity,boolean function,testing,writing,mathematical model,automata,image resolution,computer science,parallel random access machine
Boolean function,Discrete mathematics,Combinatorics,Polynomial,Circuit complexity,Semi-infinite,Upper and lower bounds,Computer science,Parallel computing,Fan-in,Reduction (recursion theory),Data parallelism
Conference
Citations 
PageRank 
References 
26
14.61
14
Authors
3
Name
Order
Citations
PageRank
Ashok K. Chandra131161215.02
Larry J. Stockmeyer243331077.31
Uzi Vishkin34359892.63