Checking quasi-identities in a finite semigroup may be computationally hard |
| |
| Authors: | M V Volkov |
| |
| Institution: | (1) Department of Mathematics and Mechanics, Ural State University, Lenina 51, Ekaterinburg, Russua |
| |
| 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. |
| |
| Keywords: | semigroup identity quasi-identity NP-completeness |
| 本文献已被 SpringerLink 等数据库收录！ |
