Back to Search
Start Over
Deciding the Existence of Minority Terms
- Source :
- Canadian Mathematical Bulletin, Canadian mathematical bulletin, 2020, Vol.63(3), pp.577-591 [Peer Reviewed Journal]
- Publication Year :
- 2020
-
Abstract
- This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x)\approx m(x,y,x)\approx m(x,x,y)\approx y$. We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.
- Subjects :
- Discrete mathematics
FOS: Computer and information sciences
Class (set theory)
68Q25 (Primary), 03B05, 08A40 (Secondary)
Computational complexity theory
General Mathematics
010102 general mathematics
0102 computer and information sciences
Mathematics - Logic
Mathematics - Rings and Algebras
Term (logic)
Decision problem
Type (model theory)
Computational Complexity (cs.CC)
01 natural sciences
Computer Science - Computational Complexity
010201 computation theory & mathematics
Rings and Algebras (math.RA)
Idempotence
FOS: Mathematics
0101 mathematics
Algebra over a field
Ternary operation
Logic (math.LO)
Mathematics
Subjects
Details
- ISSN :
- 00084395
- Database :
- OpenAIRE
- Journal :
- Canadian Mathematical Bulletin
- Accession number :
- edsair.doi.dedup.....a8eac792f78d971c1b04f94d849f3601
- Full Text :
- https://doi.org/10.4153/s0008439519000651