Leslie G. Valiant
ABSTRACT
We show that there is a combinational (acyclic) Boolean circuit of complexity 0(slog s), that can be made to compute any Boolean function of complexity s by setting its specially designated set of control inputs to appropriate fixed values. We investigate the construction of such “universal circuits” further so as to exhibit directions in which refinements of the asymptotic multiplicative constant factor in the complexity bound can be found. In this pursuit useful detailed guidance is provided by available lower bound arguments. In the final section we discuss some other problems in computational complexity that can be related directly to the graph-theoretic ideas behind our constructions. For motivation we start by illustrating some of the applications of universal circuits themselves.
- 1.V.E. BENES, Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press (1965).Google Scholar
- 2.C. BERGE, Graphs and Hypergraphs. North Holland, (1973). Google ScholarDigital Library
- 3.A. BORODIN, Some remarks on time-space and size-depth. Manuscript (1975).Google Scholar
- 4.P. ERDOS, R.L. GRAHAM and E. SZEMEREDI, On sparse graphs with dense long paths. Stanford Computer Science Report,STANCS-75-504, (1975). Google ScholarDigital Library
- 5.J. HARTMANIS and J. SIMON. On the power of multiplication in random access machines. Proc. of 15th SWAT, New Orleans, (1974), 13-23.Google ScholarDigital Library
- 6.J.E. HOPCROFT, W.J. PAUL and L.G.VALIANT, Time versus space and related problems. Proc. of 16th Symp. on FOCS, Berkeley (1975), 57-64.Google Scholar
- 7.O.B. LUPANOV, A class of circuits of functional elements, Problemy Kibemetiki, 7, 61-114 (1962).Google Scholar
- 8.Yu. P. OFMAN, A universal automaton, Trans. Moscow Math. Soc. 14, 200-215, (1965).Google Scholar
- 9.M.S. PATERSON and L.G. VALIANT, Circuit size is nonlinear in depth. Theory of Computation Report 8, University of Warwick (1975) Google ScholarDigital Library
- 10.W.J. PAUL, Lower bound and optimal strategy for a pebble game. Manuscript (1975).Google Scholar
- 11.M. PINSKER, On the complexity of a concentrator. Proc. 7th International Teletraffic Congress, Stockholm (1973).Google Scholar
- 12.N.J. PIPPENGER, The complexity theory of switching networks, TR487, Res.Lab. Elec. MIT, (1973).Google Scholar
- 13.V.R. PRATT, M.O. RABIN and L.J. STOCKMEYER, A characterization of the power of vector machines. Proc. 6th ACM Symp. on Theory of Computing, Seattle (1974) 122-134. Google ScholarDigital Library
- 14.J.E. SAVAGE. The Complexity of Computing (1974). Google ScholarDigital Library
- 15.A. WAKSMAN, A permutation network, JACM, 15, 159-163, (1968). Google ScholarDigital Library
Index Terms
- Universal circuits (Preliminary Report)
Recommendations
Efficient universal quantum circuits
Universal circuits can be viewed as general-purpose simulators for central classes ofcircuits and can be used to capture the computational power of the circuit class beingsimulated. We define and construct quantum universal circuits which are efficient ...
Area-time tradeoffs for universal VLSI circuits
An area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at the cost of lower area-time performance. In particular, if a circuit with area-time bounds (A,T) is emulated by a universal circuit with bounds (A"u,T"u), ...
Minimal universal library for n×n reversible circuits
Reversible logic plays an important role in quantum computing. Several papers have been recently published on universality of sets of reversible gates. However, a fundamental unsolved problem remains: ''what is the minimum set of gates that are ...
Comments