scientific article; zbMATH DE number 440476

MaRDI QIDQ3140633zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 16 August 1994

zbMATH Keywords

\(\text{NC}^ 1\)alternating logarithmic timeBoolean formula evaluationBoolean sentence value problempropositional formulastree- contraction

Mathematics Subject Classification ID

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

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

(17)

• A constant-space sequential model of computation for first-order logic
• Gap-languages and log-time complexity classes
• Completeness results for graph isomorphism.
• Circuits over PP and PL
• A bounded arithmetic AID for Frege systems
• 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
• scientific article; zbMATH DE number 4083547 (Why is no real title available?)
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• A unified method for placing problems in polylogarithmic depth
• scientific article; zbMATH DE number 7301717 (Why is no real title available?)
• The NP search problems of Frege and extended Frege proofs
• Frege proof system and TNC°
• A constant-space sequential model of computation for first-order logic
• Circuit complexity before the dawn of the new millennium
• On input read-modes of alternating Turing machines
• Robustness for space-bounded statistical zero knowledge

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)