Satisfiability in multi-valued circuits

DOI10.1145/3209108.3209173zbMATH Open1497.68358arXiv1710.08163OpenAlexW2963612844WikidataQ130957069 ScholiaQ130957069MaRDI QIDQ5145331FDOQ5145331

Authors: Paweł M. Idziak, Jacek Krzaczkowski 

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: Satisfiability of Boolean circuits is among the most known and important problems in theoretical computer science. This problem is NP-complete in general but becomes polynomial time when restricted either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is strictly connected with the problems of solving equations (or systems of equations) over finite algebras. The research reported in this work was motivated by a desire to know for which finite algebras $mathbfA$ there is a polynomial time algorithm that decides if an equation over $mathbfA$ has a solution. We are also looking for polynomial time algorithms that decide if two circuits over a finite algebra compute the same function. Although we have not managed to solve these problems in the most general setting we have obtained such a characterization for a very broad class of algebras from congruence modular varieties. This class includes most known and well-studied algebras such as groups, rings, modules (and their generalizations like quasigroups, loops, near-rings, nonassociative rings, Lie algebras), lattices (and their extensions like Boolean algebras, Heyting algebras or other algebras connected with multi-valued logics including MV-algebras). This paper seems to be the first systematic study of the computational complexity of satisfiability of non-Boolean circuits and solving equations over finite algebras. The characterization results provided by the paper is given in terms of nice structural properties of algebras for which the problems are solvable in polynomial time.

Full work available at URL: https://arxiv.org/abs/1710.08163

Recommendations

• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Publication:4729350
• Term equation satisfiability over finite algebras
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Satisfiability of algebraic circuits over sets of natural numbers

zbMATH Keywords

solving equationscircuit satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Congruence modularity, congruence distributivity (08B10) Networks and circuits as models of computation; circuit complexity (68Q06) Computational aspects of satisfiability (68R07)

Cited In (12)

• Supernilpotence need not imply nilpotence
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Title not available (Why is that?)
• Extending the reach of SAT with many-valued logics
• Title not available (Why is that?)
• Equation satisfiability in solvable groups
• Even Faster Algorithms for CSAT Over supernilpotent Algebras.
• Term equation satisfiability over finite algebras
• Complexity of modular circuits
• Satisfiability on mixed instances
• 3-Valued Circuit SAT for STE with Automatic Refinement
• Supernilpotent Taylor algebras are nilpotent

This page was built for publication: Satisfiability in multi-valued circuits

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