scientific article; zbMATH DE number 440476

zbMATH Open0792.68046MaRDI QIDQ3140633FDOQ3140633

Authors: Samuel R. Buss 

Publication date: 16 August 1994

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

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

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)

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)