A duality between Boolean functions

DOI10.1017/S1474748010000083MaRDI QIDQ3569370zbMATH OpenOpenAlexFDO

Authors 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 4108153
• Dualities in the class of extended Boolean functions
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• Complexity of identification and dualization of positive Boolean functions
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).

Cites work

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

Cited in

(4)

• Dualities in the class of extended Boolean functions
• Boolean functions with MacWilliams duality
• Alternative definitions of Boolean functions and relations
• Dualization of regular Boolean functions

This page was built for publication: A duality between Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569370)