The Complexity of Problems Connected with Two-element Algebras

• Authors: Tomasz A. Gorazd , Jacek Krzaczkowski
• Languages of publication: PL

Abstracts

PL

This paper presents a complete classification of the complexity of the SAT and equivalence problems for two-element algebras. Cases of terms and polynomials are considered. We show that for any fixed two-element algebra the considered SAT problems are either in P or NP-complete and the equivalence problems are either in P or coNP-complete. We show that the complexity of the considered problems, parametrized by an algebra, are determined by the clone of term operations of the algebra and does not depend on generating functions for the clone.

Keywords

PL

• Publisher: [unknown2]
• Journal: Reports on Mathematical Logic
• Year: 2011
• Volume: 46

Dates

published

2011

online

07 - 07 - 2015

Contributors

author

Tomasz A. Gorazd

author

Jacek Krzaczkowski