Infinitely generated semigroups and polynomial complexity

DOI10.1142/S0218196716500314zbMATH Open1362.68085arXiv1503.04610OpenAlexW2963143262MaRDI QIDQ5739486FDOQ5739486

Authors: J.-C. Birget 

Publication date: 15 July 2016

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

Abstract: This paper continues the functional approach to the P-versus-NP problem, begun in [1]. Here we focus on the monoid RM_2^P 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 RM_2^P, and evaluation functions. We prove that RM_2^P is not finitely generated, and use this to show separation results for time-complexity.

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

Recommendations

• Polynomial-time right-ideal morphisms and congruences
• Semigroups and one-way functions
• Inverse monoids associated with the complexity class NP
• Infinite string rewrite systems and complexity
• Generic complexity of finitely presented monoids and semigroups

zbMATH Keywords

semigroupsP vs. NPnon-finite generation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Introductory notes on Richard Thompson's groups
• Title not available (Why is that?)
• Foundations of Cryptography
• Title not available (Why is that?)
• The tale of one-way functions
• The complexity theory companion
• Semigroups and one-way functions
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Polynomial-time right-ideal morphisms and congruences

Cited In (3)

• Polynomial-time right-ideal morphisms and congruences
• Another semigroup of complexity \(n-1\)
• Inverse monoids associated with the complexity class NP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739486)