scientific article
From MaRDI portal
Publication:3140633
zbMath0792.68046MaRDI QIDQ3140633
Publication date: 16 August 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
propositional formulasalternating logarithmic timeBoolean formula evaluation\(\text{NC}^ 1\)Boolean sentence value problemtree- contraction
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items
The NP Search Problems of Frege and Extended Frege Proofs ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Gap-languages and log-time complexity classes ⋮ Completeness results for graph isomorphism. ⋮ A bounded arithmetic AID for Frege systems ⋮ On input read-modes of alternating Turing machines ⋮ A constant-space sequential model of computation for first-order logic ⋮ A constant-space sequential model of computation for first-order logic ⋮ Circuits over PP and PL ⋮ Unnamed Item ⋮ Frege proof system and TNC°
