×

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.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., \(Σ_1^1\) formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48 (1984) · Zbl 0519.03021
[2] Ajtai, M.; Ben-Or, M., A theorem on probabilistic constant depth computations, (Proceedings, 16th Annu. ACM Sympos, Theory of Comput. (1984)), 471-474
[3] Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity, (IEEE 27th Annu. Found of Comput. Sci. (1986)), 337-347
[4] 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
[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
[6] 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
[7] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042
[8] Chandra, A. K.; Stockmeyer, L. J.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, 423-439 (1984) · Zbl 0538.68038
[9] 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
[10] 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)
[11] Erdös, P.; Spencer, J., Probabilistic Methods in Combinatorics (1974), Akad. Kiadó: Akad. Kiadó Budapest · Zbl 0308.05001
[12] 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
[13] Furst, M.; Saxe, J. B.; Sipser, M., Parity, circuits, and the polynomial time hierarchy, (22nd Annu. IEEE Found. of Comput. Sci. (1981)), 260-270
[14] Gurevich, Y.; Lewls, H. R., A logic for constant depth circuits, Inform. and Control, 61, 65-74 (1984) · Zbl 0592.94023
[15] Hastad, J., Almost optimal lower bounds for small depth circuits, (18th Annu. Proceedings, ACM Sympos. Theory of Comput. (1986)), 6-20
[16] Immerman, N., Languages which capture complexity classes, (15th Annu. Proceedings, ACM Sympos. Theory of Comput. (1983)), 347-354
[17] Immerman, N.; Lander, E., Telling graphs apart: A first order approach to graph isomorphism (1984), preprint
[18] Sov. Phys. Dokl., 6, 107-108 (1961), Engl. transl. · Zbl 0104.24102
[19] McColl, W. F.; Paterson, M. S., The depth of all Boolean functions, SIAM J. Comput., 6, 373-380 (1977) · Zbl 0361.94051
[20] Minsky, M.; Papert, S., Perceptrons: An Introduction to Computational Geometry (1972), MIT Press: MIT Press Cambridge, MA · Zbl 0197.43702
[21] 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
[22] 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
[23] Pippenger, N., On networks of noisy gates, (26th Annu. IEEE Found. of Comput. Sci. (1985)), 30-38
[24] Razborov, A. A., Lower bounds for the monotone complexity of some Boolean functions, Dokl. Akad. Nauk., 281, 798-801 (1985) · Zbl 0621.94027
[25] 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
[26] English translation in: Math. Notes of the Academy of Sciences of the USSR41, 333-338.; English translation in: Math. Notes of the Academy of Sciences of the USSR41, 333-338.
[27] Reif, J. H., On threshold circuits and polynomial computation, (Proceedings, 2nd Structure in Complexity Theory Conf (1987)), 118-125
[28] Rumelhardt, D. E.; McClelland, J. L., (Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1 (1986), MIT Press: MIT Press Cambridge, MA)
[29] 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
[30] Skyum, S., A measure in which Boolean negation is exponentially powerful, Inform. Process. Lett., 17, 125-128 (1983) · Zbl 0533.94004
[31] Skyum, S.; Valiant, L. G., A complexity theory based on Boolean algebra, J. Assoc. Comput. Mach., 32, 484-502 (1985) · Zbl 0633.68032
[32] 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
[33] Spencer, J., Ten Lectures on the Probabilistic Method (1987), SIAM: SIAM Philadelphia · Zbl 0703.05046
[34] Turán, Gy., The critical complexity of graph properties, Inform. Process. Lett., 18, 151-153 (1984) · Zbl 0542.68026
[35] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.