Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân tách các lớp phức tạp liên quan đến chương trình nhánh ω-bị ràng buộc
Tóm tắt
Chúng tôi phát triển một lý thuyết về giao tiếp trong các chương trình nhánh cung cấp các giới hạn dưới mũ về kích thước của các chương trình nhánh bị ràng buộc luân phiên. Lý thuyết của chúng tôi dựa trên khái niệm đại số của chương trình nhánh Ω, ω: ℕ → ℝ, một đồng hình bán trường, mà tổng quát hóa các chương trình nhánh thông thường, chương trình nhánh Ω [M2] và chương trình nhánh MOD p [DKMW]. Do những giới hạn dưới mũ nhất định và các giới hạn trên đa thức về kích thước của các chương trình nhánh ω-bị ràng buộc luân phiên, chúng tôi có thể phân tách các lớp phức tạp tương ứng Nℒ ba, co-Nℒ ba ⊕ℒ ba, và MOD p -ℒ ba, với p là số nguyên tố, với nhau, và với các lớp tương ứng với các chương trình nhánh bị ràng buộc chiều dài tuyến tính không nhớ được nghiên cứu trong quá khứ.
Từ khóa
#lớp phức tạp #chương trình nhánh #ω-bị ràng buộc #giới hạn dưới mũ #giới hạn trên đa thứcTài liệu tham khảo
N. Alon, W. Maass: Meanders, Ramsey Theory and Lower Bounds,J. Comput. System Sci.,37 (1988), 118–129.
G. Buntrock, C. Damm, U. Hertrampf, Ch. Meinel: Structure and Importance of Logspace-MOD-classes,Proc. STACS '91, LNCS, Vol. 480, Springer-Verlag, Berlin, pp. 360–371. Also inMath. Systems Theory,25 (1992), 223–237.
D. Damm, M. Krause, Ch. Meinel, S. Waack: Separating Restricted MOD p -Branching Program Classes, Informatik-Preprint 3 (1990), Humboldt-University, Berlin.
M. Krause: Separating ⊕ℒ from ℒ,co-Nℒ andAL=P for Oblivious Turing Machines of Linear Access Time,Proc. MFCS '90, LNCS, Springer-Verlag, Berlin, pp. 385–391.
M. Krause, Ch. Meinel, S. Waack: Separating the Eraser Turing Machine Classes ℒ e ,Nℒ e co-Nℒ e andP e , Proc. MFCS '88, LNCS, Vol. 324, Springer-Verlag, Berlin, pp. 405–413.
M. Krause, Ch. Meinel, S. Waack: Separating Complexity Classes Related to Certain Input Oblivious Logarithmic Space Bounded Turing Machines,Proc. 4th IEEE Structure in Complexity Theory, 1989, pp. 240–259.
S. Lang:Algebra, Addison-Wesley, Reading, MA.
C. Y. Lee: Representation of Switching Functions by Binary Decision Programs,Bell System Tech. J.,38 (1959), 985–999.
Ch. Meinel: Polynomial Size Ω-Branching Programs and Their Computational Power,Proc. STACS '88, LNCS Vol. 294, Springer Verlag, Berlin, pp. 81–90.
Ch. Meinel:Modified Branching Programs and Their Computational Power, LNCS, Vol. 370, Springer-Verlag, Berlin, 1989.
Ch. Meinel, S. Waack: Upper and Lower Bounds for Certain Graph-Accessibility-Problems on Bounded Alternating Branching Programs, Proc. MFCS '91, LNCS, Vol. 520, Springer-Verlag, Berlin, pp. 337–345.
P. Pudlák, S. Žak: Space Complexity of Computations, Preprint, University of Prague, 1983.
W. Savitch: Relations Between Nondeterministic and Deterministic Tape Complexities,J. Comput. System Sci., 4 (1970), 177–192.
I. Wegener: The Complexity of Branching Programs and Decision Trees for Clique Functions,J. Assoc. Comput. Mach.,35(2) (1988), 461–471.