Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The complexity of problems connected with two-element algebras

Gorazd T., Krzaczkowski J.

Reports on Mathematical Logic

2011

Vol. 46

91-108

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 equiva- lence 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 al- gebra and does not depend on generating functions for the clone.