Polynomial-time right-ideal morphisms and congruences

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We continue with the functional approach to the P-versus-NP problem, begun in [J. C. Birget, Semigroups and one-way functions, Int. J. Algebra Comput. 25(1-2) (2015) 3-36; J. C. Birget, Infinitely generated semigroups and polynomial complexity, Int. J. Algebra Comput. 26(04) (2016) 727-750.] We previously constructed a monoid P that is non-regular iff NP P. We now construct homomorphic images of P with interesting properties. In particular, the homomorphic image polyP of P is finitely generated, and is non-regular iff P NP. The group of units of polyP is the famous Richard Thompson group V.

Original languageEnglish (US)
Pages (from-to)791-835
Number of pages45
JournalInternational Journal of Algebra and Computation
Volume28
Issue number5
DOIs
StatePublished - Aug 1 2018

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • P -versus- NP
  • Semigroups
  • regular semigroups

Fingerprint Dive into the research topics of 'Polynomial-time right-ideal morphisms and congruences'. Together they form a unique fingerprint.

  • Cite this