scientific article; zbMATH DE number 3999297

MaRDI QIDQ4725752zbMATH OpenFDO

Authors Klaus-Jörn Lange

Publication date 1986

zbMATH Keywords

bounded quantificationlogarithmic alternation hierarchynondeterministic many-one log-space reductionsNP-complete sets

Mathematics Subject Classification ID

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

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

(12)

• [[: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 ramified recurrence
• scientific article; zbMATH DE number 4024792 (Why is no real title available?)
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• scientific article; zbMATH DE number 1222092 (Why is no real title available?)
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• Inductive counting below LOGSPACE
• Empty alternation
• Predicate characterizations in the polynomial-size hierarchy
• A Characterization of Alternating Log Time by First Order Functional Programs
• On log-time alternating Turing machines of alternation depth k
• Complexity classes of equivalence problems revisited

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)