Infinitely generated semigroups and polynomial complexity

DOI10.1142/S0218196716500314zbMath1362.68085arXiv1503.04610OpenAlexW2963143262MaRDI QIDQ5739486

Jean-Camille Birget

Publication date: 15 July 2016

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.04610

zbMATH Keywords

semigroupsP vs. NPnon-finite generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Regular semigroups (20M17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Polynomial-time right-ideal morphisms and congruences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Introductory notes on Richard Thompson's groups
• The tale of one-way functions
• Foundations of Cryptography
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• Polynomial-time right-ideal morphisms and congruences
• Semigroups and one-way functions
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• The complexity theory companion

This page was built for publication: Infinitely generated semigroups and polynomial complexity