Journal
Article title
Authors
Content
Full texts:
Title variants
Languages of publication
Abstracts
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.
Publisher
Journal
Year
Volume
Physical description
Dates
published
2011
online
07 - 07 - 2015
Contributors
author
author
References
Document Type
Publication order reference
Identifiers
YADDA identifier
bwmeta1.element.ojs-issn-2084-2589-year-2011-volume-46-article-2882