×

On uniformity within \(NC^ 1\). (English) Zbl 0719.68023

The class \(NC^ 1\) of languages recognized by log-depth polynomial-size circuits is considered. The main goal is to study circuit complexity classes within \(NC^ 1\) in a uniform setting. It is shown that families of circuits defined by first-order formulas and a uniformity corresponding to deterministic log-time reductions are equivalent. This leads to a natural notion of uniformity for low-level circuit complexity classes. In this connection the expressive power of the first-order logic with and without the BIT pedicate is explored. New quantifiers (modular, counting, majority and group quantifiers) are also introduced to express languages in larger complexity classes. Recent results on the characterization of \(NC^ 1\) in terms of constant-width branching programs are shown to still hold true in uniform setting.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03D20 Recursive functions and relations, subrecursive hierarchies
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M., \(Σ_1^i\) formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48 (1983) · Zbl 0519.03021
[2] Allender, E., \(P\)-uniform circuit complexity, J. Assoc. Comput. Mach., 36, No. 4, 912-928 (1989) · Zbl 0697.68031
[3] Barrington, D. A., Bounded-Width Branching Programs, (Ph.D. thesis, M.I.T. Dept. of Mathematics, Technical Report TR-361 (May 1986), M.I.T. Laboratory for Computer Science) · Zbl 0837.68056
[4] Barrington, D. A., Bounded-width polynomial-size branching recognize exactly those languages in \(NC^1\), J. Comput. System Sci., 38, No. 1, 150-164 (1989) · Zbl 0667.68059
[5] Barrington, D. A.M.; Immerman, N.; Straubing, H., On uniformity within \(NC^1\), (Structure in Complexity Theory: Third Annual Conference (1988), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 47-59
[6] Barrington, D. A.M.; Compton, K.; Straubing, H.; Tidrien, D., Regular languages in \(NO^1\), (J. Comput. System Sci. (Oct. 1988), Boston College), to appear, Technical report BCCS-88-02
[7] Barrington, D. A.M.; Therien, D., Finite monoids and the fine structure of \(NC^1\), J. Assoc. Comput. Mach., 35, No. 4, 941-952 (1988) · Zbl 0667.68068
[8] 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
[9] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 6, 305-322 (1977) · Zbl 0356.68059
[10] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705
[11] Buss, S. R., The Boolean formula value problem is in ALOGTIME, (19th ACM STOC Symp. (1987)), 123-131
[12] Buss, S.; Cook, S.; Gupta, A.; Ramachandran, V., An optimal parallel algorithm for formula evaluation (1989), University of Toronto, typescript · Zbl 0825.68424
[13] Chandra, A. K.; Fortune, S.; Lipton, R., Unbounded fan-in circuits and associative functions, (15th ACM STOC Symp. (1983)), 52-60
[14] Chandra, A. K.; Kozen, C. D.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[15] Chandra, A. K.; Stockmeyer, L. J.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, No. 2, 423-439 (1984) · Zbl 0538.68038
[16] Cook, S. A., A taxonomy of problems with fast parallel algorithms, Inform. and Control, 64, 2-22 (1985) · Zbl 0575.68045
[17] Eilenberg, S., (Automata, Languages, and Machines, Vol. B (1976), AcademicPress: AcademicPress New York)
[18] Enderton, H., A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York · Zbl 0298.02002
[19] Furst, M.; Saxe, J. B.; Sipser, M., Parity, circuits, and the polynomial-time hierarchy, Math. Systems Theory, 17, 13-27 (1984) · Zbl 0534.94008
[20] Hajnal, A.; Maass, W.; Pudlak, P.; Szegedy, M.; Turán, G., Threshold circuits of bounded depth, (28th IEEE FOCS Symp. (1987)), 99-110
[21] Immerman, N., Relational queries computable in polynomial time, Inform. and Control, 68, 86-104 (1986) · Zbl 0612.68086
[22] Immerman, N., Languages which capture complexity classes, SIAM J. Comput., 16, No. 4, 760-778 (1987) · Zbl 0634.68034
[23] Immerman, N., Expressibility as a complexity measure: Results and directions, (Second Structure in Complexity Theory Conf. (1987)), 194-202
[24] Immerman, N., Nondeterministic space is closed under complementation, SIAM J. Comput., 17, No. 5, 935-938 (1988) · Zbl 0668.68056
[25] Immerman, N., Expressibility and parallel complexity, SIAM J. Comput., 18, 625-638 (1989) · Zbl 0688.68038
[26] Krohn, K. B.; Rhodes, J.; Tilson, B., (Arbib, M. A., The Algebraic Theory of Machines, Languages, and Semigroups (1968), Academic Press: Academic Press New York)
[27] Ladner, R. E., Application of model-theoretic games to discrete linear orders and finite automata, Inform. and Control, 33, 281-303 (1977) · Zbl 0387.68037
[28] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[29] Lipton, R. J., Model theoretic aspects of computational complexity, (19th IEEE FOCS Symp. (1978)), 193-200
[30] McNaughton, R.; Papert, S., Counter-Free Automata (1971), MIT Press: MIT Press Cambridge, MA · Zbl 0232.94024
[31] Parberry, I.; Schnitger, G., Parallel computation with threshold functions, J. Comput. System Sci., 36, No. 3, 278-302 (1988) · Zbl 0652.68064
[32] Pin, J. E., Varieties of Formal Languages (1986), Plenum: Plenum New York · Zbl 0632.68069
[33] Razborov, A. A., Math. Notes Acad. Sci. USSR, 41, No. 4, 333-338 (1987), English transl. · Zbl 0632.94030
[34] Reif, J. H., On threshold circuits and polynomial computation, (Second Structure in Complexity Theory Conference (1987)), 118-123
[35] Ruzzo, W. L., On uniform circuit complexity, J. Comput. System Sci., 21, No. 2, 365-383 (1981) · Zbl 0462.68013
[36] Smolensky, R., Algebraic methods in the theory of lower bounds for Boolean circuit complexity, (19th ACM STOC Symp. (1987)), 77-82
[37] Spira, P. M., On time-hardware complexity tradeoffs for Boolean functions, (Proceedings, 4th Hawaii Symposium on System Sciences (1971), Western Periodicals: Western Periodicals North Hollywood, CA), 525-527
[38] Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[39] Stockmeyer, L.; Vishkin, U., Simulation of parallel random access machines by circuits, SIAM J. Comput., 13, No. 2, 409-422 (1984) · Zbl 0533.68048
[40] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. Pure Appl. Algebra, 18, 305-318 (1979) · Zbl 0414.20056
[41] Straubing, H.; Therien, D.; Thomas, W., Regular languages defined with generalized quantifiers, (Proceedings, 15th ICALP (1988)), 561-575
[42] Thomas, W., Classifying regular events in symbolic logic, J. Comput. System Sci., 25, 360-376 (1982) · Zbl 0503.68055
[43] Vardi, M., Complexity of relational query languages, (14th ACM STOC Symp. (1982)), 137-146
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.