On the upper bounds for complexities of discrete functions

DOI10.1142/S1793557122501790MaRDI QIDQ5876808zbMATH OpenOpenAlexFDO

Authors Slavcho Shtrakov

Publication date 2 February 2023

Published in Asian-European Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793557122501790

zbMATH Keywords

identification minorminor complexityminor decision diagramseparable setsubfunction

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• On discrete universality of composite functions
• Complexity of nonuniform computations for certain discrete problems
• Complexity of functions: Some questions, conjectures, and results
• scientific article; zbMATH DE number 3903259
• The complexity of functions on lattices
• scientific article; zbMATH DE number 619539
• On the representation of rational functions of bounded complexity
• scientific article; zbMATH DE number 139637
• On total functions, existence theorems and computational complexity
• scientific article; zbMATH DE number 3979140

Cites work

• Essential arities of term operations in finite algebras
• Essential arity gap of Boolean functions
• Essential Variables and Separable Sets in Universal Algebra
• Finite symmetric functions with non-trivial arity gap
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 3216991 (Why is no real title available?)
• On finite functions with non-trivial arity gap
• On the classification of Boolean functions.
• Parametrized arity gap

This page was built for publication: On the upper bounds for complexities of discrete functions

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