Abstract
We exhibit a 10-element semigroup Q such that the question “Does a given quasi-identity hold in Q?” is co-NP-complete while the question “Does a given identity hold in Q?” can be answered in linear time.
Similar content being viewed by others
References
Bergman, C., and G. Slutzki, ‘Complexity of some problems concerning varieties and quasi-varieties of algebras’, SIAM J. Comput. 30:359–382, 2000.
Clifford, A. H., and G. B. Preston, The Algebraic Theory of Semigroups, Vol. I, Amer. Math. Soc., 1961.
Garey, M. R., and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
Klíma, O., ‘Complexity issues of checking identities in finite monoids’, submitted.
Mashevitsky, G. I., ‘On identities in varieties of completely simple semigroups over abelian groups’, Modern Algebra, Leningrad, 81–89, 1978 (in Russian).
Ore, O., Theory of Graphs, Amer. Math. Soc., 1962.
Papadimitriou, C. H., Computational Complexity, Addison-Wesley Publishing Company, 1994.
Seif, S., ‘The Perkins semigroup has co-NP-complete term-equivalence problem’, submitted.
Author information
Authors and Affiliations
Additional information
Special issue of Studia Logica: “Algebraic Theory of Quasivarieties” Presented by M. E. Adams, K. V. Adaricheva, W. Dziobiak, and A. V. Kravchenko
Rights and permissions
About this article
Cite this article
Volkov, M.V. Checking quasi-identities in a finite semigroup may be computationally hard. Stud Logica 78, 349–356 (2004). https://doi.org/10.1007/s11225-005-0356-5
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11225-005-0356-5