Une dualité entre fonctions booléennes

DOI10.1017/S1474748010000083zbMath1192.68301OpenAlexW2098688519MaRDI QIDQ3569370

Bruno Poizat

Publication date: 18 June 2010

Published in: Journal of the Institute of Mathematics of Jussieu (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s1474748010000083

zbMATH Keywords

parallelizationparsimonious reductioncomplexity of computationsvaliantarithmetic circuits and termsmalod

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• The complexity of computing the permanent
• Completeness and reduction in algebraic complexity theory
• Characterizing Valiant's algebraic complexity classes
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• On the Time Necessary to Compute Switching Functions