Full-text resources of PSJD and other databases are now available in the new Library of Science.
Visit https://bibliotekanauki.pl
Preferences help
Polish version English version Language
enabled [disable] Abstract
Number of results

Results found: 1

Number of results on page
first rewind previous Page / 1 next fast forward last

Search results

help Sort By:

help Limit search:
first rewind previous Page / 1 next fast forward last
1
Publication available in full text mode
Content available

The Complexity of Problems Connected with Two-element Algebras

100%
Gorazd T. A., Krzaczkowski J.
Reports on Mathematical Logic
|
2011
|
vol. 46
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.
first rewind previous Page / 1 next fast forward last
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.