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

inverse monoids NP one-way functions

Mathematics Subject Classification ID

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

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.

Review text

The basic unsolved complexity-theoretic problems \(\mathrm{P}\neq\mathrm{NP?}\) and existence of one-way functions are tackled considering algebraic properties of partial polynomially balanced functions acting on finite strings over the alphabet \(A = \{ 0,1\} \) computable by a deterministic polynomial-time Turing machine; a function \(f:{A^*} \to {A^*}\) is polynomially balanced iff there exists a polynomial \(p\) such that \(|f(x)| \le p(|x|)\), \(|x| \le |p(x)|\). It is known, that \(\mathrm{P}\neq \mathrm{NP}\) iff there exists a polynomially balanced function computable in polynomial time by a deterministic Turing machine which does not have an inverse that is computable in polynomial time, and functions that are polynomial-time computable and polynomially balanced, but have no inverse of that type, are one-way functions. Here, the author studies properties of several algebras of such functions: the monoid fP of polynomially balanced polynomial-time computable functions, the reverse monoid invfP of injective functions in fP that have an inverse in fP, the inverse monoid invfP(NP) of functions computed by injective Turing machines with NP oracle, the monoid cofP of functions in invfP(NP) that have an inverse in fP, the monoid injfP of injective functions in fP; e.g., it is shown that the monoid cofP is finitely generated, and \(\mathrm{P}\neq\mathrm{NP}\) iff \(\mathrm{invfP} \ne \mathrm{cofP}\) iff \(\mathrm{cofP} \ne \mathrm{invfP(NP)}\) iff cofP is not regular.

Recommendations

Cites work

Cited in

(5)

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)