Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access

DOI10.1051/ITA/1992260605071MaRDI QIDQ4032302zbMATH OpenOpenAlexFDO

Authors Matthias Krause

Publication date 1 April 1993

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92430

zbMATH Keywords

lower boundsTuring machinesparity branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4213443
• scientific article; zbMATH DE number 17548
• Superlinear lower bounds for bounded-width branching programs
• Separating complexity classes related to bounded alternating ?-branching programs
• scientific article; zbMATH DE number 4051004

Cites work

• scientific article; zbMATH DE number 3987204 (Why is no real title available?)
• scientific article; zbMATH DE number 4051004 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 17536 (Why is no real title available?)
• scientific article; zbMATH DE number 17548 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• Modified branching programs and their computational power
• Nondeterministic Space is Closed under Complementation
• On the complexity of branching programs and decision trees for clique functions
• On the power of parity polynomial time
• On uniform circuit complexity
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

Cited in

(7)

• scientific article; zbMATH DE number 827986 (Why is no real title available?)
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Separating complexity classes related to bounded alternating ?-branching programs
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• scientific article; zbMATH DE number 1796950 (Why is no real title available?)

This page was built for publication: Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032302)