scientific article; zbMATH DE number 440476
From MaRDI portal
Publication:3140633
zbMATH Open0792.68046MaRDI QIDQ3140633FDOQ3140633
Authors: Samuel R. Buss
Publication date: 16 August 1994
Title of this publication is not available (Why is that?)
Recommendations
propositional formulasalternating logarithmic timeBoolean formula evaluation\(\text{NC}^ 1\)Boolean sentence value problemtree- contraction
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cited In (16)
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Circuit complexity before the dawn of the new millennium
- Completeness results for graph isomorphism.
- Frege proof system and TNC°
- A constant-space sequential model of computation for first-order logic
- A constant-space sequential model of computation for first-order logic
- The NP search problems of Frege and extended Frege proofs
- Title not available (Why is that?)
- A generalization of Spira's theorem and circuits with small segregators or separators
- Title not available (Why is that?)
- A unified method for placing problems in polylogarithmic depth
- Gap-languages and log-time complexity classes
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- Circuits over PP and PL
- A bounded arithmetic AID for Frege systems
- On input read-modes of alternating Turing machines
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 Q3140633)