Infinitely generated semigroups and polynomial complexity
| Autor: | Jean-Camille Birget |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Monoid
Pure mathematics Polynomial General Mathematics 010102 general mathematics P versus NP problem Functional approach 0102 computer and information sciences 01 natural sciences Morphism 010201 computation theory & mathematics Polynomial complexity Free monoid 0101 mathematics Focus (optics) Mathematics |
| Zdroj: | International Journal of Algebra and Computation. 26:727-750 |
| ISSN: | 1793-6500 0218-1967 |
| DOI: | 10.1142/s0218196716500314 |
| Popis: | This paper continues the functional approach to the [Formula: see text]-vs.-[Formula: see text] problem, begun in [J. C. Birget, Semigroups and one-way functions, Internat. J. Algebra Comput. 25 (1–2) (2015) 3–36]. Here, we focus on the monoid [Formula: see text] of right-ideal morphisms of the free monoid, that have polynomial input balance and polynomial time-complexity. We construct a machine model for the functions in [Formula: see text], and evaluation functions. We prove that, [Formula: see text] is not finitely generated, and use this to show separation results for time-complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|