Inverse monoids associated with the complexity class NP

DOI10.1007/s00233-018-9990-xzbMath1419.68053arXiv1703.02519OpenAlexW2594086588MaRDI QIDQ666698

Jean-Camille Birget

Publication date: 11 March 2019

Published in: Semigroup Forum (Search for Journal in Brave)

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

zbMATH Keywords

inverse monoidsone-way functionsNP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Inverse semigroups (20M18)

Cites Work

• Randomness conservation inequalities; information and independence in mathematical theories
• Time/Space Trade-Offs for Reversible Computation
• Semigroups and one-way functions
• Logical Reversibility of Computation
• The complexity theory companion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Inverse monoids associated with the complexity class NP