PL EN


2011 | 46 | 90-108
Article title

THE COMPLEXITY OF PROBLEMS CONNECTED WITH TWO-ELEMENT ALGEBRAS

Selected contents from this journal
Title variants
Languages of publication
EN
Abstracts
EN
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
Year
Issue
46
Pages
90-108
Physical description
Document type
ARTICLE
Contributors
  • Tomasz Gorazd, Theoretical Computer Science Department, Jagiellonian University, Krakow, Poland
References
Document Type
Publication order reference
Identifiers
CEJSH db identifier
11PLAAAA10197
YADDA identifier
bwmeta1.element.86220755-f061-39c9-98b7-fa9f1fe99535
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.