## 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: | 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. |

Pages: | 9 |

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

Paper: |