×

Polynomial size \(\Omega\)-branching programs and their computational power. (English) Zbl 0705.68052

Summary: In the following new types of branching programs, so-called \(\Omega\)- branching programs, \(\Omega \subseteq B_ 2\), are introduced. The complexity classes related to polynomial-size \(\Omega\)-branching programs will be completely classified. In addition to identifying a new class \({\mathcal P}_{\{\oplus \}-BP}=\oplus L/poly\) between L/poly and P/poly, new characterizations of such fundamental space complexity classes like \(NL/poly=co\)-NL/poly and P/poly are obtained. Using these characterizations we relate the complexity of the mentioned classes to those of some extremely restricted problems resembling the graph accessibility problem.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barrington, D. A., Bounded-width polynomial size branching programs recognize exactly those languages in \(NC^1\), (Proceedings, 18th ACM STOC (1986)), 1-5
[2] Budach, L., Klassifizierungsprobleme und das Verhältnis von deterministischer und nichtdeterministischer Raumkomplexität (1982), manuscript · Zbl 0569.68039
[3] Cobham, A., The recognition problem for the set of perfect squares, (Research paper RC-1704 (1966), IBM Watson Research Center)
[4] Chandra, A. K.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, No. 2, 423-439 (1984) · Zbl 0538.68038
[5] Chandra, A. K.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[6] Goldschlager, L. M.; Parberry, I., On the construction of parallel computers from various bases of Boolean functions, Theoret. Comput. Sci., 43, 43-58 (1986) · Zbl 0604.68054
[7] Immerman, N., (Nondeterministic Space Is Closed under Complement (1987), Yale University), Tech. Report 552
[8] Karp, R. M.; Kipton, R. J., Some connections between nonuniform and uniform complexity classes, (Proceedings, 12th ACM STOC (1980)), 302-309
[9] Krause, M.; Meinel, Ch.; Waack, S., Separating the eraser Turing machine classes \(L_e\), \(NL_e\), co-\(NL_e\), and \(P_e \), (Proceedings MFCS 88. Proceedings MFCS 88, Lecture Notes in Comput. Sci., Vol. 324 (1988), Springer-Verlag: Springer-Verlag New York/Berlin), 405-413
[10] Meinel, Ch., \(p\)-projection reducibility and the complexity classes \(L\) (nonuniform) and NL (nonuniform), (Proceedings, MFCS 86. Proceedings, MFCS 86, Lecture Notes in Comput. Sci., Vol. 233 (1986), Springer-Verlag: Springer-Verlag New York/Berlin), 527-533
[11] Meinel, Ch., Rudiments of a branching program based complexity theory (1986), Sekt. Mathematik, Humboldt-University: Sekt. Mathematik, Humboldt-University Berlin, Preprint Nr. 127
[12] Meinel, Ch., The nonuniform complexity classes \(NC^1, L\), and \(NL\), EIK, 23, No. 10/11, 545-558 (1987) · Zbl 0638.68028
[13] Post, E., Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 163-185 (1921) · JFM 48.1122.01
[14] Papadimitriou, C. H.; Zachos, S. K., Two remarks on the power of counting (1982), MIT, preprint MIT/LCS/TM-228 · Zbl 0506.68039
[15] Pudlak, P.; Z̆ak, S., Space complexity of computations (1983), University of Prague, preprint
[16] Savitch, W., Relations between nondeterministic and deterministic tape complexities, J. Comput. System Sci, 4, 177-192 (1970) · Zbl 0188.33502
[17] Savage, J. E., (The Complexity of Computing (1976), Wiley: Wiley New York) · Zbl 0391.68025
[18] Skyum, S.; Valiant, L. G., A complexity theory based on Boolean algebra, (Proceedings, 22nd IEEE FOCS (1981)), 244-253 · Zbl 0633.68032
[19] Szelepcsenyi, R., The method of forcing for nondeterministic automata, Bull. EATCS, 33, 96-99 (1987) · Zbl 0664.68082
[20] Wegener, I., Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Inform. and Control, 62, Nos. 2/3 (1984) · Zbl 0544.68035
[21] Wegener, I., (The Complexity of Boolean Functions (1987), Wiley-Teubner: Wiley-Teubner Stuttgart) · Zbl 0623.94018
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.