Inverse monoids associated with the complexity class NP (Q666698)

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.