scientific article; zbMATH DE number 3999297

zbMATH Open0616.68050MaRDI QIDQ4725752FDOQ4725752

Klaus-Jörn Lange

Publication date: 1986

Title of this publication is not available (Why is that?)

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\)]]

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)

Cited In (9)

• Title not available (Why is that?)
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• Inductive counting below logspace
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• A Characterization of Alternating Log Time by First Order Functional Programs
• Complexity classes of equivalence problems revisited
• 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)