scientific article; zbMATH DE number 3999297

MaRDI QIDQ4725752zbMATH OpenFDO

Authors Klaus-Jörn Lange

Publication date 1986

zbMATH Keywords

NP-complete setsbounded quantificationlogarithmic alternation hierarchynondeterministic many-one log-space reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 45125
• The alternation hierarchy for sublogarithmic space is infinite
• The Sublogarithmic Alternating Space World
• scientific article; zbMATH DE number 4024792
• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]

Cited in

(11)

• scientific article; zbMATH DE number 4024792 (Why is no real title available?)
• Predicate characterizations in the polynomial-size hierarchy
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• A Characterization of Alternating Log Time by First Order Functional Programs
• Complexity classes of equivalence problems revisited
• On log-time alternating Turing machines of alternation depth k
• Inductive counting below LOGSPACE
• A characterization of alternating log time by ramified recurrence
• Empty alternation
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic

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 Q4725752)