Satisfiability in MultiValued Circuits

DOI10.1137/18M1220194MaRDI QIDQ5080482zbMATH OpenOpenAlexFDO

Authors Paweł M. Idziak, Jacek Krzaczkowski

Publication date 31 May 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/18m1220194

zbMATH Keywords

circuit equivalencecircuit satisfiabilitysolving equations

Mathematics Subject Classification ID

Structure theory of algebraic structures (08A05) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Satisfiability in multi-valued circuits
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• scientific article; zbMATH DE number 4114007
• Term equation satisfiability over finite algebras
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS

Cites work

• A concrete ideal multiplication for algebraic systems and its relation to congruence distributivity
• Absorption and directed Jónsson terms
• Complexity issues of checking identities in finite monoids
• Computational complexity of solving equation systems
• Congruence modular varieties with small free spectra
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Dichotomies for classes of homomorphism problems involving unary functions
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Equivalence and equation solvability problems for the alternating group A₄.
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Geometrical methods in congruence modular algebras
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 4035895 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 5030273 (Why is no real title available?)
• Intermediate problems in modular circuits satisfiability
• Mal'cev varieties
• Non-uniform automata over groups
• On solvability of systems of polynomial equations
• On the number of finite Mal'tsev algebras
• Results on the equivalence problem for finite groups.
• Some applications of higher commutators in Mal'cev algebras
• STACS 2004
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Term equation satisfiability over finite algebras
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of equivalence for commutative rings
• The complexity of problems connected with two-element algebras
• The complexity of satisfiability problems
• The complexity of solving equations over finite groups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of the equivalence problem for nonsolvable groups
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The equivalence problem for finite rings
• The extended equivalence and equation solvability problems for groups
• The structure of finite algebras
• Tractability and learnability arising from algebras with few subpowers

Cited in

(5)

• Extending the reach of SAT with many-valued logics
• Satisfiability on mixed instances
• 3-Valued Circuit SAT for STE with Automatic Refinement
• Circuit equivalence in 2-nilpotent algebras
• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: Satisfiability in MultiValued Circuits

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