Infinitely generated semigroups and polynomial complexity

DOI10.1142/S0218196716500314MaRDI QIDQ5739486zbMATH OpenOpenAlexFDO

Authors J.-C. 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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Free semigroups, generators and relations, word problems (20M05) Regular semigroups (20M17)

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.

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

Cites work

• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3448564 (Why is no real title available?)
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Foundations of Cryptography
• Introductory notes on Richard Thompson's groups
• Polynomial-time right-ideal morphisms and congruences
• Semigroups and one-way functions
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• The complexity theory companion
• The tale of one-way functions

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)