The complexity of AND-decomposition of Boolean functions

DOI10.1016/j.dam.2019.07.005zbMath1481.94166OpenAlexW2963804349MaRDI QIDQ2181249

P. G. Emelyanov, Denis K. Ponomaryov

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.07.005

zbMATH Keywords

computational complexitypolynomial factorizationdisjoint decompositionconjunctive decomposition

Mathematics Subject Classification ID

Boolean functions (94D10)

Related Items (1)

On the relationship between the complexity of decidability and decomposability of first-order theories

Uses Software

• JBool

Cites Work

• On decidability of the decomposability problem for finite theories
• Exploiting functional properties of Boolean functions for optimal multi-level design by bi-decomposition
• An improvement on the complexity of factoring read-once Boolean functions
• On a polytime factorization algorithm for multilinear polynomials over \(\mathbb{F}_2\)
• Factorization of Boolean polynomials: parallel algorithms and experimental evaluation
• A polynomial Time Delta-Decomposition algorithm for positive DNFs
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables
• Modern Computer Algebra
• On Tractability of Disjoint AND-Decomposition of Boolean Formulas
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of AND-decomposition of Boolean functions