scientific article; zbMATH DE number 4213443

MaRDI QIDQ3359756zbMATH OpenFDO

Authors Matthias Krause

Publication date 1990

zbMATH Keywords

branching programslogarithmic space-bounded Turing machineslower bound techniqueparty acceptation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• scientific article; zbMATH DE number 17548
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
• Separating complexity classes related to bounded alternating ?-branching programs

Cited in

(11)

• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
• Separating complexity classes related to bounded alternating ?-branching programs
• scientific article; zbMATH DE number 827986 (Why is no real title available?)
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Separating counting communication complexity classes
• On oblivious branching programs of linear length
• Problems complete for \(\oplus L\)

This page was built for publication:

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