Inverse monoids associated with the complexity class NP

DOI10.1007/S00233-018-9990-XMaRDI QIDQ666698zbMATH OpenOpenAlexFDO

Authors J.-C. 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

one-way functionsinverse monoidsNP

Mathematics Subject Classification ID

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

Abstract: We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way functions (with respect to worst-case complexity) exist.

Recommendations

• Semigroups and one-way functions
• scientific article; zbMATH DE number 3990863
• Infinitely generated semigroups and polynomial complexity
• On some natural complete operators
• A survey of one-way functions in complexity theory
• scientific article; zbMATH DE number 4213444
• Pseudo-free families and cryptographic primitives
• On the circuit-size of inverses
• One-way functions and circuit complexity
• One-way permutations and self-witnessing languages

Cites work

• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1761434 (Why is no real title available?)
• scientific article; zbMATH DE number 774488 (Why is no real title available?)
• Logical Reversibility of Computation
• Randomness conservation inequalities; information and independence in mathematical theories
• Semigroups and one-way functions
• The complexity theory companion
• Time/Space Trade-Offs for Reversible Computation

Cited in

(5)

• Infinitely generated semigroups and polynomial complexity
• Polynomial-time right-ideal morphisms and congruences
• Structural analysis of the complexity of inverse functions
• CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
• Semigroups and one-way functions

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

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