Satisfiability in multi-valued circuits

Authors: Pawel Idziak and Jacek Krzaczkowski

Paper Information

Title:Satisfiability in multi-valued circuits
Authors:Pawel Idziak and Jacek Krzaczkowski
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:circuit satisfiability, Constraint Satisfaction Problem, solving equations, structure theory

ABSTRACT. Satisfiability of Boolean circuits 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 connected with solving equations over finite algebras. We want to characterize finite algebras A with polynomial time algorithm deciding if an equation over A has a solution. We are also looking for polynomial time algorithms deciding 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 (in terms of nice structural algebraic properties) for a very broad class of algebras from congruence modular varieties, including groups, rings, lattices and their extensions.

Talk:Jul 11 12:00 (Session 64D)