Semigroups and one-way functions
From MaRDI portal
Publication:5246500
DOI10.1142/S0218196715400019zbMath1328.68072arXiv1306.1447MaRDI QIDQ5246500
Publication date: 21 April 2015
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.1447
Free semigroups, generators and relations, word problems (20M05) Regular semigroups (20M17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability) ⋮ Inverse monoids associated with the complexity class NP ⋮ Infinitely generated semigroups and polynomial complexity ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ Prime decomposition theorem for arbitrary semigroups: General holonomy decomposition and synthesis theorem
Cites Work
- A construction which can be used to produce finitely presented infinite simple groups
- Monoid generalizations of the Richard Thompson groups.
- One-way permutations, computational asymmetry and distortion.
- One way functions and pseudorandom generators
- ON THE CIRCUIT-SIZE OF INVERSES
- THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID Mk, 1 AND THEIR COMPLEXITY
- New directions in cryptography
- Foundations of Cryptography
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- Computational Complexity
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- Unnamed Item
- Unnamed Item
