scientific article; zbMATH DE number 440476

MaRDI QIDQ3140633zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 16 August 1994

zbMATH Keywords

propositional formulasalternating logarithmic timeBoolean formula evaluation\(\text{NC}^ 1\)Boolean sentence value problemtree- contraction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• An Optimal Parallel Algorithm for Formula Evaluation
• A simple parallel tree contraction algorithm
• Parallel Tree Contraction Part 2: Further Applications
• Parallel restructuring and evaluation of expressions
• Size-depth tradeoffs for Boolean formulae

Cited in

(16)

• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Completeness results for graph isomorphism.
• Circuit complexity before the dawn of the new millennium
• 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
• scientific article; zbMATH DE number 7301717 (Why is no real title available?)
• A generalization of Spira's theorem and circuits with small segregators or separators
• scientific article; zbMATH DE number 4083547 (Why is no real title available?)
• Gap-languages and log-time complexity classes
• A unified method for placing problems in polylogarithmic depth
• 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)