Satisfiability in MultiValued Circuits

DOI10.1137/18M1220194OpenAlexW2766935653MaRDI QIDQ5080482

Jacek Krzaczkowski, Paweł M. Idziak

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

solving equationscircuit equivalencecircuit satisfiability

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On solvability of systems of polynomial equations
• Some applications of higher commutators in Mal'cev algebras
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of equivalence for commutative rings
• Non-uniform automata over groups
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• A concrete ideal multiplication for algebraic systems and its relation to congruence distributivity
• Mal'cev varieties
• The complexity of solving equations over finite groups
• Dichotomies for classes of homomorphism problems involving unary functions
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The equivalence problem for finite rings
• Results on the equivalence problem for finite groups.
• Complexity issues of checking identities in finite monoids
• Computational Complexity of Solving Equation Systems
• TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Geometrical methods in congruence modular algebras
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Absorption and directed Jónsson terms
• Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras.
• Intermediate problems in modular circuits satisfiability
• The complexity of the equivalence problem for nonsolvable groups
• STACS 2004
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Congruence modular varieties with small free spectra

This page was built for publication: Satisfiability in MultiValued Circuits