## Threshold circuits of bounded depth.(English)Zbl 0801.68052

Summary: We examine a powerful model of parallel computation: polynomial size threshold circuits of bounded depth (the gates compute threshold functions with polynomial weights). Lower bounds are given to separate polynomial size threshold circuits of depth 2 from polynomial size threshold circuits of depth 3 and from probabilistic polynomial size circuits of depth 2. With regard to the unreliability of bounded depth circuits, it is shown that the class of functions computed reliably with bounded depth circuits of unreliable $$\land$$, $$\lor$$, $$\neg$$ gates is narrow. On the other hand, functions computable by bounded depth, polynomial-size threshold circuits can also be computed by such circuits of unreliable threshold gates. Furthermore we examine to what extent imprecise threshold gates (which behave unpredictably near the threshold value) can compute nontrivial functions in bounded depth and a bound is given for the permissible amount of imprecision. We also discuss threshold quantifiers and prove an undefinability result for graph connectivity.

### MSC:

 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text:

### References:

  Ajtai, M., $$Σ_1^1$$ formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48 (1984) · Zbl 0519.03021  Ajtai, M.; Ben-Or, M., A theorem on probabilistic constant depth computations, (Proceedings, 16th Annu. ACM Sympos, Theory of Comput. (1984)), 471-474  Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity, (IEEE 27th Annu. Found of Comput. Sci. (1986)), 337-347  Barrington, D. A., Bounded-width, polynomial size branching programs recognize exactly those languages in $$NC^1$$, (18th Annu. Proceedings, ACM Sympos Theory of Comput. (1986)), 1-5  Barrington, D. A.; Thérien, D., Finite monoids and the fine structure of $$NC^1$$, (19th Annu. Proceedings, ACM Sympos. Theory of Comput. (1987)), 101-109  Beame, P. W.; Cook, S. A.; Hoover, H. J., Log depth circuits for division and related problems, SIAM J. Comput., 15, 994-1003 (1986) · Zbl 0619.68047  Bollobás, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042  Chandra, A. K.; Stockmeyer, L. J.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, 423-439 (1984) · Zbl 0538.68038  Chor, B.; Goldreich, O., Unbiased bits from sources of weak randomness and probabilistic communication complexity, (26th Annu. IEEE Found. of Comput. Sci. (1985)), 429-442  Dobrushin, R. L.; Ortyukov, S. J., Upper bound for the redundancy of self-correcting arrangements of unreliable functional elements, Problems Inform. Transmission, 13, 59-65 (1977)  Erdös, P.; Spencer, J., Probabilistic Methods in Combinatorics (1974), Akad. Kiadó: Akad. Kiadó Budapest · Zbl 0308.05001  Fagin, R.; Klawe, M. M.; Pippenger, N. J.; Stockmeyer, L. J., Bounded depth, polynomial size circuits for symmetric functions, Theoret. Comput. Sci., 36, 239-250 (1985) · Zbl 0574.94024  Furst, M.; Saxe, J. B.; Sipser, M., Parity, circuits, and the polynomial time hierarchy, (22nd Annu. IEEE Found. of Comput. Sci. (1981)), 260-270  Gurevich, Y.; Lewls, H. R., A logic for constant depth circuits, Inform. and Control, 61, 65-74 (1984) · Zbl 0592.94023  Hastad, J., Almost optimal lower bounds for small depth circuits, (18th Annu. Proceedings, ACM Sympos. Theory of Comput. (1986)), 6-20  Immerman, N., Languages which capture complexity classes, (15th Annu. Proceedings, ACM Sympos. Theory of Comput. (1983)), 347-354  Immerman, N.; Lander, E., Telling graphs apart: A first order approach to graph isomorphism (1984), preprint  Sov. Phys. Dokl., 6, 107-108 (1961), Engl. transl. · Zbl 0104.24102  McColl, W. F.; Paterson, M. S., The depth of all Boolean functions, SIAM J. Comput., 6, 373-380 (1977) · Zbl 0361.94051  Minsky, M.; Papert, S., Perceptrons: An Introduction to Computational Geometry (1972), MIT Press: MIT Press Cambridge, MA · Zbl 0197.43702  Von Neumann, J., Probabilistic logics and the synthesis of reliable organisms from unreliable components, (Shannon, C. E.; McCarthy, J., Automata Studies (1956), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ), 43-98  Parberry, I.; Schnitger, G., Parallel computation with threshold functions, (Selman, A. L., Structure in Complexity Theory. Structure in Complexity Theory, Lect. Notes in Comput. Sci., Vol. 223 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 272-290  Pippenger, N., On networks of noisy gates, (26th Annu. IEEE Found. of Comput. Sci. (1985)), 30-38  Razborov, A. A., Lower bounds for the monotone complexity of some Boolean functions, Dokl. Akad. Nauk., 281, 798-801 (1985) · Zbl 0621.94027  Razborov, A. A., Lower bounds for the size of circuits of bounded depth with basis { ∨, ⊕ }, Mat. Zametki, 41, 598-607 (1987), preprint · Zbl 0632.94030  Reif, J. H., On threshold circuits and polynomial computation, (Proceedings, 2nd Structure in Complexity Theory Conf (1987)), 118-125  Rumelhardt, D. E.; McClelland, J. L., (Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1 (1986), MIT Press: MIT Press Cambridge, MA)  Simon, H. U., A tight Ω(log log $$n)$$ bound on the time for parallel RAM’s to compute nondegenerate Boolean functions, (Found. in Comput. Theory, 1983. Found. in Comput. Theory, 1983, Lecture Notes in Computer Science, Vol. 158 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 151-153  Skyum, S., A measure in which Boolean negation is exponentially powerful, Inform. Process. Lett., 17, 125-128 (1983) · Zbl 0533.94004  Skyum, S.; Valiant, L. G., A complexity theory based on Boolean algebra, J. Assoc. Comput. Mach., 32, 484-502 (1985) · Zbl 0633.68032  Smolensky, R., Algebraic methods in the theory of lower bounds for Boolean circuit complexity, (19th Annu. Proceedings, ACM Sympos. Theory of Comput. (1987)), 77-82  Spencer, J., Ten Lectures on the Probabilistic Method (1987), SIAM: SIAM Philadelphia · Zbl 0703.05046  Turán, Gy., The critical complexity of graph properties, Inform. Process. Lett., 18, 151-153 (1984) · Zbl 0542.68026  Yao, A. C., Separating the polynomial-time hierarchy by oracles, (26th Annu IEEE Found. of Comput. Sci. (1985)), 1-10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.