Satisfiability in MultiValued Circuits

DOI10.1137/18M1220194OpenAlexW2766935653MaRDI QIDQ5080482FDOQ5080482

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

Recommendations

• Satisfiability in multi-valued circuits
• 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

zbMATH Keywords

solving equationscircuit equivalencecircuit satisfiability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Extending the reach of SAT with many-valued logics
• Satisfiability on mixed instances
• 3-Valued Circuit SAT for STE with Automatic Refinement

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)