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.
All Science Journal Classification (ASJC) codes
- P -versus- NP
- regular semigroups