Inverse monoids associated with the complexity class NP
J.C. Birget

arXiv:1703.02519v1 [] 7 Mar 2017

6 March 2017

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.

1

Introduction

We give a few definitions before motivating the monoid approach to the P versus NP problem. Some
of these notions appeared already in [3].
By function we mean a partial function A∗ → A∗ , where A is a finite alphabet (usually, A = {0, 1}),
and A∗ denotes the set of all finite strings over A. Let Dom(f ) (⊆ A∗ ) denote the domain of f , i.e.,
{x ∈ A∗ : f (x) is defined}; and let Im(f ) (⊆ A∗ ) denote the image (or range) of f , i.e., {f (x) : x ∈
Dom(f )}. The length of x ∈ A∗ is denoted by |x|. The restriction of f to X ⊆ A∗ is denoted by f |X ,
and the identity function on X is denoted by idX or id|X .
Definition 1.1 (inverse, co-inverse, mutual inverse) A function f ′ is an inverse of a function
f iff f ◦ f ′ ◦ f = f . In that case we also say that f is a co-inverse of f ′ . If f ′ is both an inverse and
a co-inverse of f , we say that f ′ is a mutual inverse of f , or that f ′ and f are mutual inverses (of
each other).1
It is easy to see that f ′ is an inverse of f iff for every y ∈ Im(f ): f ′ (y) is defined and f ′ (y) ∈ f −1 (y).
Hence, in particular, Im(f ) ⊆ Dom(f ′ ). Also, f ′ is an inverse of f iff f ◦ f ′ |Im(f ) = idIm(f ) .
An element f of a semigroup S is called regular (or more precisely, regular in S) iff there exists
f ′ ∈ S such that f f ′ f = f ; in that case, f ′ is called an inverse of f (more precisely, an inverse in S of
f ), and f is called a co-inverse of f ′ (in S). A semigroup S is called regular iff all the elements of S
are regular in S; see e.g. [6, 5]. An inverse semigroup is, by definition, a semigroup S such that every
element of S has exactly one mutual inverse in S; see e.g. [9, 6, 5].
The connection between the P versus NP problem and inverses comes from the following well
known characterization: P 6= NP iff there exists a function that is computable in polynomial time
(by a deterministic Turing machine) and that is polynomially balanced, but that does not have an
inverse that is computable in polynomial time; see e.g. [8] p. 33, and Section 1 of [3]. A function f :
A∗ → A∗ is called polynomially balanced iff there exists a polynomial p such that for all x ∈ Dom(f ):
|f (x)| ≤ p(|x|) and |x| ≤ p(|f (x)|). Functions that are polynomial-time computable and polynomially
balanced, but that have no inverse of that type, are one-way functions in the sense of worst-case
complexity.2 In [3] this characterization of the P versus NP problem was reformulated in terms of
regularity of semigroups, by introducing the monoid fP, defined as follows.
1
The terminology about inverses varies. In semigroup theory, f ′ such that f f ′ f = f is called a semi-inverse or a
pseudo-inverse of f , in numerical mathematics f ′ is called a generalized inverse, in ring theory and in category theory it
is called a weak inverse or a von Neumann inverse. In semigroup theory the term “inverse” of f is only used if f ′ f f ′ = f ′
holds in addition to f f ′ f = f . Co-inverses don’t seem to have a name in the literature.
2
One-way functions in this sense are not necessarily useful for cryptography, but they are relevant for P vs. NP.

1

Definition 1.2.
fP = {f : f is a function A∗ → A∗ that is polynomially balanced, and
computable by a deterministic polynomial-time Turing machine}.
In particular, when f ∈ fP then Dom(f ) is in P. The set fP is closed under composition of functions,
and the identity function is in fP, so fP is a monoid. The above characterization of P 6= NP now
becomes:
P 6= NP iff fP is a non-regular monoid.
We will use some more definitions that apply to functions.
For any function f : X → Y , the equivalence relation modf on Dom(f ) is defined by: x1 modf x2
iff f (x1 ) = f (x2 ). The set of equivalence classes of modf is {f −1 (y) : y ∈ Im(f )}.
A choice set for f is, by definition, a subset of Dom(f ) that contains exactly one element of each
modf -class. A choice function for f is, by definition, any inverse f ′ of f such that Dom(f ′ ) = Im(f ).
A choice function f ′ maps each element y ∈ Im(f ) injectively to an element of f −1 (y), and every
modf -class contains exactly one element of Im(f ′ ); so Im(f ′ ) is a choice set. For a choice function f ′
we have f ◦ f ′ = f ◦ f ′ |Im(f ) = idIm(f ) , hence f f ′ f = f ; we also have f ′ f f ′ = f ′ ; more generally, if
f1′ , f2′ are two choice functions for the same function f then f2′ f f1′ = f2′ . A choice function for f is
uniquely determined by f and a choice set.
A representative choice function for f is, by definition, any function r such that Im(r) ⊆ Dom(r) =
Dom(f ), Im(r) is a choice set for f , modr = modf , and r|Im(r) = idIm(r) . Thus, r maps each modf -class
[x]f to one and the same chosen element of [x]f . It follows that r is an idempotent; and if r1 , r2 are
two representative choice functions for the same function f then r2 ◦ r1 (.) = r2 (.). If f ∈ fP and if in
addition r ∈ fP, then f ≡L r (by Prop. 2.1 in [3]). So in that case f is a regular element of fP, since it
is L-equivalent to an idempotent. Hence, if every function in fP had a representative choice function
in fP, then fP would be regular, which would imply P = NP.
There is a one-to-one correspondence between the choice functions of f and the representative
choice functions: If c is a choice function then ρc (.) = c ◦ f (.) is a representative choice function; and
if r is a representative choice function of f then vr (.) = r ◦ f −1 (.) is a choice function (where f −1 is
the inverse relation of f , and ◦ is composition of relations). Moreover, if r is a representative choice
function of f then ρvr = r; and if c is a choice function of f then vρc = c.
For functions in general, the existence of a choice function, the existence of a representative choice
function, and the existence of a choice set, are equivalent to the axiom of choice. Because of this
connection we are especially interested in inverses f ′ of f that are choice functions, i.e., that satisfy
Dom(f ′ ) = Im(f ).
These three formulations of the axiom of choice can also be considered for fP: (1) “Every f ∈ fP
has an inverse in fP.” Equivalently, “f has a choice function in fP”, and also equivalently, “f has a
mutual inverse in fP”. (2) “Every f ∈ fP has a representative choice function in fP.” (3) “Every f ∈ fP
has a choice set in P.” It is an open problem problem whether the three statements are true.
We saw that (1) is true iff P = NP. Moreover, (1) implies (2); indeed, if f has an inverse f ′ ∈ fP then
′
f f is a representative choice function in fP. And (2) implies (3); indeed, if r ∈ fP is a representative
choice function of f , then r is regular (being an idempotent), hence Im(r) belongs to P by Prop. 1.9 in
[3]; and Im(r) is a choice set for r and for f . It remains an open problem whether other implications
between (1), (2), (3) hold. Nevertheless, we have the following.
Proposition 1.3 There exists an injective one-way function (for worst-case complexity) iff there
exists a one-way function that has a choice set in P.
Proof. If g ∈ fP is injective then Dom(g) is a choice set for g, and Dom(g) ∈ P. If g is also one-way,
then it is therefore a one-way function with a choice set in P.
The converse follows immediately from the next Lemma. ✷

2

Lemma 1.4 If f ∈ fP has a choice set C ∈ P, but f is not regular (i.e., (3) holds but (1) does not),
then the restriction f |C is an injective one-way function.
Proof. Since f ∈ fP and C ∈ P then we have f |C ∈ fP. Moreover, if C is a choice set for f then f |C is
injective. And if C is a choice set, any inverse of f |C is also an inverse of f . Hence f |C has no inverse
in fP (since f is not regular). ✷
The motivation for this paper is based on the following simple observation: If f : A∗ → A∗ is any
partial function and if f ′ is an inverse of f , then the restriction f ′ |Im(f ) is an injective inverse of f .
Moreover, if f ∈ fP and f ′ ∈ fP, then Im(f ) ∈ P (by Prop. 1.9 in [3]); hence f ′ |Im(f ) ∈ fP. Thus we
have: P 6= NP iff there exists f ∈ fP such that f has no injective inverse in fP.
The classes P and NP are defined in terms of sets of strings (“formal languages”). To add more
structure we use functions, and we characterized P and NP by properties of monoids of functions [3].
Our next step, in the present paper, is to characterize P versus NP by properties of inverse monoids,
and of groups. However, whether this approach will help solve the P versus NP problem, remains to
be seen.
Overview: In Section 2 we introduce the monoid invfP consisting of all injective regular functions
in fP. We prove that every regular function in fP has an inverse in invfP, and that invfP is a maximal
inverse submonoid of fP.
In Section 3 we show that the polynomial-time polynomially balanced injective Turing machines
form a machine model for invfP, i.e., that a function f belongs to invfP iff f is computed by such a
Turing machine. We conclude from this that invfP is finitely generated. We also consider polynomialtime polynomially balanced injective Turing machines with an NP-oracle, and we show that the set
invfP(NP) of functions computed by such Turing machines is a finitely generated inverse monoid. To
prove the latter, we show that there exist languages that are NP-complete with respect to one-one
reductions in invfP. We show that every function in fP has an inverse in invfP(NP) .
In Section 4 we show that invfP 6= invfP(NP) iff P 6= NP. We introduce the set cofP of all functions
in invfP(NP) that have an inverse in fP, i.e., that are a co-inverse of a function in fP. We show that this
is a finitely generated monoid. We prove that P 6= NP iff invfP 6= cofP, iff cofP 6= invfP(NP) , iff cofP is
not regular.
We also introduce the monoid injfP of all injective functions in fP; injfP is also equal to invfP(NP) ∩
fP. We show that the inverse monoid invfP is the set of the regular elements of injfP. Hence, injective
one-way functions (for worst-case complexity) exist iff invfP 6= injfP. We do not know whether injfP is
finitely generated; if it turns out that injfP is not finitely generated then P 6= NP.
In Section 5 we show that every element of fP is equivalent (with respect to inversive-reductions)
to an element of fP that has an inverse in a subgroup of invfP(NP) .
Notation for the monoids used, and their definition:
fP
invfP
invfP(NP)
cofP
injfP

Definition
Definition
Definition
Definition
Definition

1.2
2.2
3.6
4.10
4.12

(polynomially balanced polynomial-time computable functions)
(injective functions in fP that have an inverse in fP)
(functions computed by injective Turing machines with NP-oracle)
(functions in invfP(NP) that have an inverse in fP)
(injective functions in fP)

The relation between these monoids is shown in Figure 1 (after Prop. 4.13).

2

Injective inverses of regular elements

For any function f : A∗ → A∗ , we will be interested in inverses f ′ of f that satisfy Dom(f ′ ) = Im(f );
such inverses are necessarily injective. Moreover, when Dom(f ′ ) = Im(f ) we not only have f f ′ f = f ,
but also f ′ f f ′ = f ′ . So f and f ′ are mutual inverses.
3

An injective inverse f ′ , as above, has exactly one inverse f ′′ that satisfies Dom(f ′′ ) = Im(f ′ ), namely
= f ′−1 (the set-theoretic inverse function of f ′ ); moreover, Im(f ′−1 ) = Im(f ). And f ′−1 = f |Im(f ′ ) ,
i.e., the restriction of f to the choice set Im(f ′ ) of f ′ .
Here are some more simple facts about inverses: If f ′ is a mutual inverse of f then Im(f ′ ) ⊆
Dom(f ). Moreover, f ′ is a mutual inverse of f iff Im(f ′ ) = Im(f ′ |Im(f ) ). Note that f ′ |Im(f ) is the
choice function determined by f ′ , so Dom(f ′ |Im(f ) ) = Im(f ). Thus an inverse f ′ is a mutual inverse of
f iff Im(f ′ ) is the choice set determined by f ′ in Dom(f ). As a consequence, a mutual inverse f ′ of
f is injective iff Dom(f ′ ) = Im(f ).
f ′′

Proposition 2.1 If g1 and g2 are injective regular elements of fP, then g2 ◦ g1 is also injective and
regular in fP.
Proof. The composite of injective functions is obviously injective. Since gi is regular (for i = 1, 2),
it has the injective regular function gi−1 as an inverse. Indeed, Im(gi ) ∈ P, and gi−1 = gi′ |Im(gi ) for any
inverse gi′ ∈ fP of gi ; hence, gi−1 ∈ fP. Thus, the injective function g1−1 ◦ g2−1 is a mutual inverse of
g2 ◦ g1 , and Dom(g1−1 ◦ g2−1 ) = Im(g2 ◦ g1 ). ✷
Note that in general, the product of regular elements in fP need not be regular (unless P = NP); but
by the above proposition, the product of injective regular elements is regular.
Definition 2.2 Let invfP denote the set of injective regular elements of fP.
Corollary 2.3 The set invfP of injective regular elements of fP is an inverse monoid. Every regular
element of fP has an inverse in invfP.
✷
Corollary 2.3 implies that P = NP iff every element of fP has an inverse in invfP.
Another motivation for invfP will be seen in Prop. 3.11, where is is shown that there exist languages
that are NP-complete with respect to one-one reductions in invfP.
A monoid M1 is called an inverse submonoid of a monoid M iff M1 is submonoid of M , and M1 is
an inverse monoid by itself. So, an element of M1 has exactly one mutual inverse in M1 , but it could
have additional mutual inverses in M .
Proposition 2.4 The inverse submonoid invfP is a maximal inverse submonoid of fP; i.e., if M is
an inverse monoid such that invfP ⊆ M ⊆ fP, then invfP = M .
Proof. Let M be an inverse submonoid such that invfP ⊆ M ⊆ fP. For a contradiction, let us assume
that invfP 6= M . Then M contains a non-injective element f , which is regular (since M is inverse).
Since f is regular, f has a choice function f1′ ; since f is non-injective, f has at least one other choice
function f2′ .
Moreover, since f1′ ∈ invfP, we can pick f2′ in such a way that f2′ ∈ invfP too. Indeed, let x1 , x2 ∈
Dom(f ) be such that f (x1 ) = f (x2 ), and x1 is in the choice set Im(f1′ ), and x2 6∈ Im(f1′ ). Let τ be the
transposition of x1 and x2 (and τ is the identity elsewhere). Then f2′ = f1′ ◦ τ belongs to invfP, and is
the same as f1′ , except that x2 has replaced x1 in the choice set.
Since the choice functions f1′ , f2′ belong to invfP (⊆ M ), f has two mutual inverses in M , which
implies that M is not an inverse monoid. ✷
Remarks. (1) Prop. 2.4 holds, whether fP is regular or not.
(2) An inverse submonoid of fP need not consist of injective functions only, and the submonoid invfP is
not the only maximal inverse submonoid of fP. E.g., fP contains non-injective idempotents, and these
are contained in maximal inverse monoids that are different from invfP (since they contain non-injective
elements).
Proposition 2.5 A maximal subgroup of fP, and more generally, any L-class of fP, is either disjoint
from invfP or entirely contained in invfP.
4

Proof. An L-class of fP that intersects invfP contains injective elements, hence it consist entirely of
injective elements (by Prop. 2.1 in [3]). Also, an L-class of fP that intersects invfP contains regular
elements, hence it consist entirely of regular elements (it is a well-known fact from semigroup theory
that if a D-class contains regular elements then it consists entirely of regular elements; see e.g. [5, 6]).
Hence, this L-class consists entirely of regular injective elements, hence it is contained in invfP. ✷
On the other hand, every regular R-class of fP intersects both invfP and fP − invfP. Indeed, for
every regular element f ∈ fP we have f ≡R idIm(f ) (and Im(f ) is in P when f is regular). But a
regular R-class always contains some non-injective elements (by Prop. 2.1 in [3]).

3

Computing inverses

There is a machine model that exactly characterizes the injective inverses of the regular elements of
fP, namely the polynomially balanced polynomial-time injective Turing machines. As a consequence
we will prove that invfP is finitely generated.
Turing machines of the above type, with an NP-oracle added, form a model of computation for
another inverse monoid, invfP(NP) (given in Def. 3.6), which contains some injective inverses for every
element of fP.

3.1

Injective Turing machines

There is a very simple machine model for the elements of invfP, namely the polynomially balanced
polynomial-time injective Turing machines. A deterministic Turing machine is called injective iff the
transition table of the Turing machine describes a (finite) injective function; for details, see [1, 2].
The reverse of a Turing machine M is the machine obtained by reversing every transition of M
(and also switching start and accept states). The reverse of a deterministic Turing machine M is is
not deterministic, unless M is injective.
Remark. In the literature, injective Turing machines are called “reversible”, because of historic
connections with the study of computation as a “reversible process” (in the sense of thermodynamics).
However, calling an injective Turing machine “reversible” can be misleading, since the transitions
obtained by reversing an injective Turing machine M are not part of M (but of a different machine).
Proposition 3.1.
(1) The reverse of a polynomially balanced polynomial-time injective Turing machine is also a polynomially balanced polynomial-time injective Turing machine. If a function f is polynomially balanced
and it is computed by a polynomial-time injective Turing machine, then f −1 is also polynomially balanced and it is computed by a polynomial-time injective Turing machine.
(2) There exists a polynomial-time injective Turing machine (that is not polynomially balanced)
whose reverse does not have polynomial time-complexity. There exists an injective function g that is
computed by a polynomial-time injective Turing machine, whose inverse g−1 is not computable by a
polynomial-time Turing machine.
Proof. (1) An injective Turing machine M , computing an injective function f , can be run in reverse.
This yields a new injective Turing machine M ′ , computing f −1 . If M runs in polynomial time, with
polynomial pT (.), and it is polynomially balanced, with polynomial pB (.), then M ′ is also polynomially
balanced, with polynomial pB (.) too, and runs in polynomial time, with polynomial bound pT ◦ pB (.).
(2) An example of such a function is
m
g : a(2 ) 7−→ am , for all m ∈ N,
where a is a fixed letter; g is undefined on any input that is not of the form ak with k a power of 2.
Obviously, g is injective and polynomial-time computable, but not polynomially balanced. Hence,
g−1 is not computable in polynomial time, since its output is exponentially longer than its input.
However, g is computable in linear time by the following injective Turing machine: We use a Turing
5

machine with a rubber tape for the input, and an ordinary tape for the output. A rubber tape is a tape
on which one can not only replace one letter by another one (as on an ordinary tape), but where one
also can insert a letter or remove a letter (in one transition). A rubber tape can easily be simulated
by two stacks; a stack is a special case of an ordinary tape. The machine that computes g works as
follows, in outline. It has a main loop (“while . . .”); it has an inner loop that is executed at the
beginning of the body of the main loop. For this inner loop, the machine uses two states to count the
input positions modulo 2, and erases every second a (which is possible on a rubber tape). When the
right end of the input tape is reached, the state must correspond to an even number of letters a on
the input tape (otherwise, the machine rejects and has no output for this input). At this moment,
one a is printed on the output tape.
while the input tape is not empty:
// main loop
{
in a loop, erase every second a on the input tape; // inner loop
when the right end of the input tape is reached, // after the inner loop
if the number of letters a read in the inner loop was even:
then add an a on the output tape;
else reject;
in a loop, move the head of the input tape back to the left end; // 2nd inner loop
}
This program runs in linear time, and every step is injective.
This injective Turing machine for g can be reversed, which yields an injective Turing machine for
g−1 with exponential time-complexity. ✷
Proposition 3.2 Let h: A∗ → A∗ be an injective function. Then h belongs to invfP iff h is
polynomially balanced, and is computable by some polynomial-time injective Turing machine.
Proof. For any h ∈ invfP, h is injective and computable in polynomial time; moreover, h−1 ∈ invfP,
i.e., h−1 is also injective and computable in polynomial time. Hence, Bennett’s theorem is applicable
(see [1, 2]), so h can be computed by a polynomial-time injective deterministic Turing machine. Also,
since both h and h−1 are computable in polynomial time, h is polynomially balanced. Conversely, if
h is polynomially balanced and is computed by a polynomial-time injective Turing machine, then h−1
can also be computed by such a machine, by Prop. 3.1. ✷
We saw in the Introduction that f ∈ fP is regular iff f has an inverse in invfP. Hence by Prop. 3.2,
we have for all f ∈ fP:
f is regular iff f has an inverse that is computable by a polynomially balanced polynomial-time
injective Turing machine. And P = NP iff every f ∈ fP has an inverse that can be computed by a
polynomially balanced polynomial-time injective Turing machine.

3.2

Evaluation functions and finite generation

Based on the transition table of a Turing machine, one can easily check whether this Turing is deterministic, and whether it is injective. Moreover, we saw in [3] and [4] that one can add a built-in
polynomial time bound and balance bound into the transition table. This can be done for injective
Turing machines too, without destroying injectiveness; indeed, a time bound p(|x|) can be computed
injectively on input x (where p is a stored polynomial, described by its degree and coefficients). So
we can design a set of strings (programs) that describe all polynomially balanced polynomial-time
injective Turing machines. And just as in [3], for every polynomial q(n) = a · (nk + 1), there exists an
evaluation function evq that evaluates all injective Turing machine programs with built-in polynomial
less than q. The details are the same as in [3], and injectiveness doesn’t change any reasoning. We
call such a Turing machine description an invfP-program.
A Turing machine with program w will be denoted by Mw ; we denote the injective input-output
function of Mw by φw .
6

An evaluation function maps a pair (w, x), consisting of a program w and an input x (for Mw ), to
(w, φw (x)), i.e., to that same program and the program-output. In order to represent a pair of strings
by one string we use the prefix code {00, 01, 11}, and the function code(.) defined by
code(0) = 00,

code(1) = 01.

The pair of strings (w, x) is represented unambiguously by code(w) 11 x, where 11 acts as a separator
(since {00, 01, 11} is a prefix code). The evaluation function injEvq is defined by

injEvq code(w) 11 x = code(w) 11 φw (x)

for any invfP-program w with built-in polynomial less than q, and any x ∈ Dom(φw ). The function
injEvq is itself injective and polynomially balanced and polynomial-time computable (with a larger
polynomial than q however). Moreover, injEvq is regular; indeed, the unique mutual inverse of injEvq
−1
is injEv−1
q , and this belongs to fP since φw (x) is injective and regular, i.e., φw ∈ fP for every invfPprogram w. So, injEvq ∈ invfP.
The proof of Prop. 4.5 in [3], showing that fP is finitely generated, goes through without much
change. We use the relation
(⋆)

φw (x) = π2′ |w′ |+2 ◦ contr ◦ recontr2 m ◦ injEvq ◦ reexpand2m ◦ expand ◦ πcode(w) 11 (x),

where w is a program of a polynomially balanced polynomial-time injective Turing machine with
built-in polynomial < q, and w′ = co2m+1 ◦ ex2m+1 (w). See Section 4 of [3] for the definition of contr,
recontr, reexpand, expand, πn′ , πv , co, and ex. The role of expand and reexpand is to increase the input
length, so as to reduce complexity by a padding argument; when complexity is below q, injEvq can be
applied; after that, recontr and contr remove the padding.
The functions contr, recontr, injEvq , reexpand, expand, and πcode(w) 11 are injective and regular (i.e.,
they belong to invfP). In the relation (⋆) we can replace π2′ |w′ |+2 by the injective regular function
′
πcode(w)
: code(w) 11 x 7−→ x. Moreover, πcode(w) is generated by {π0 , π1 }, and π2′ |w′ |+2 is generated
11
by {π0′ , π1′ }.
Thus, φw is generated by the finite set of functions {contr, recontr, injEvq , reexpand, expand, π0 ,
π1 , π0′ , π1′ } ⊂ invfP, and we have:
Proposition 3.3 The inverse monoid invfP is finitely generated, as a monoid.

✷

For every invfP-program w, we can easily obtain an invfP-program (let’s call it w′ ) for φ−1
w ; for this
purpose we simply reverse the injective Turing machine described by w. Thus the function w 7→ w′ is
polynomially balanced and polynomial-time computable; moreover, w 7→ w′ is injective and involutive,
so the function w 7→ w′ is in invfP. Thus we proved:
Proposition 3.4 There exists a function proginv ∈ invfP such that proginv (w) is an invfP-program for
φ−1
✷
w , for every invfP-program w.
We would like to extend the above function proginv to all “regular” fP-programs, i.e., the fPprograms w for which φw is regular in fP. We can do this by using universal search, a.k.a. Levin
search; this is described in [10, 11], but without much detail; for a detailed exposition, see for example
[12] (Theorem 7.21 in the 1993 edition). In the general regular case, proginv (w) is just a program such
that φproginv (w) has polynomial time-complexity, but proginv (w) does not have a built-in polynomial for
its time-complexity; Levin search is not able to explicitly find such a polynomial, although it exists if
φw is regular.
Proposition 3.5 (inversion by Levin search). There exists a function proginv ∈ fP such that for
every fP-program w, proginv (w) is a program for a mutual inverse of φw satisfying Dom(φproginv (w) ) =
Im(φw ).

7

The time-complexity of φproginv (w) is Θ(Tφw ) + Θ(Tw′ ), where Θ(Tφw ) is (up to big-Θ) the optimal
time-complexity of all Turing machines for φw , and Θ(Tw′ ) is (up to big-Θ) the optimal time-complexity
of all Turing machines for all mutual inverses of φw .
In particular:
If φw is regular then φprog inv (w) has polynomial time-complexity. But the program proginv (w) does
not have a built-in polynomial for its time-complexity, i.e., proginv (w) is not an fP-program.
If φw is not regular, proginv (w) is a non-polynomial-time program. The time-complexity of φproginv (w)
has nevertheless an exponential upper bound.
Proof. In our version of universal search the input has the form (w, y), where w is an fP-program,
and y is a possible output of the Turing machine Mw . Remark: For convenience we write (w, y) as a
pair of words, but our universal search will actually use the single word code(w) 11 y.
The output of universal search is (w, x) such that x ∈ φ−1
w (y), if w is an fP-program, and y ∈ Im(φw )
(i.e., if φ−1
(y)
=
6
∅);
there
is
no
output
if
w
is
not
an
fP-program,
or if y 6∈ Im(φw ). Thus universal
w
′
search computes a mutual inverse ev of the general evaluation function ev for fP. Both ev′ and ev
are partial recursive (but they do not belong to fP since no polynomial bound is prescribed, as for
evq ). Since we restrict universal search to fP-programs (hence, with built-in polynomial complexity
bound), the domain of ev is decidable; so universal search is an algorithm (that always halts). Indeed,
by rejecting programs with no polynomial time bound, the search algorithm also rejects programs
that do not halt. And for a polynomial program with known polynomial complexity, inversion has a
predictable exponential-time upper-bound.
For a fixed w in the input, universal search computes ev′ (w, ·) = (w, φ′w (.)), where φ′w (.) is a mutual
inverse of φw . For the details of the universal search algorithm we refer to [12] (proof of Theorem 7.21,
p. 412 in the 1993 edition). From the specification of universal search and w, we immediately derive
a program for ev′ (w, ·); this program is called proginv (w). Since proginv (w) is easily obtained from w,
the function proginv (.) belongs to fP.
The program proginv (w) has minimum time-complexity Θ(Tφw ) + Θ(Tw′ ); this is proved in [12].
It follows that the time-complexity of proginv (w) has an exponential upper bound (since w is an fPprogram). It also follows that proginv (w) is a polynomial-time program if φw is regular, i.e., if φw has
a polynomial-time inverse. But universal search does not find out explicitly what that polynomial is,
so proginv (w) cannot have a built-in polynomial for its time-complexity bound; i.e., proginv (w) is not
an fP-program. ✷

3.3

Injective Turing machines with NP-oracle

In preparation for the next Section, we generalize polynomially balanced polynomial-time injective
Turing machines by adding an oracle from NP.
Definition 3.6 By invfP(NP) we denote the set of all functions computed by polynomially balanced
polynomial-time injective Turing machines, with an oracle belonging to NP.
By Prop. 3.2 we have: invfP ⊆ invfP(NP) .
An injective Turing machine with an oracle is a deterministic and injective machine. Indeed, it
computes deterministically and injectively inbetween oracle transitions. And in an oracle transition
the only change is in the state, which goes from the query state qqu to either qyes or qno ; the contents
and head positions of the tapes (including the query tape) remain unchanged. The next transition
will go to a different state than qyes or qno , so the state qyes (or qno ) uniquely determines the previous
state qqu . Thus, an oracle transition is deterministic and injective.
The reverse of an injective Turing machine with an oracle has a slightly different format than an
an injective Turing machine with an oracle, as described above. Indeed, in an oracle call the following
transition happens: The machine is in the query state qqu and then it enters an answer state, either
8

qyes or qno , according as the word on the query tape belongs to the oracle set or not. (Before a query,
a word is written on the query tape; this happens in the course of a possibly long computation. After
a query, the computation continues, and during this computation the query tape content may be
gradually erased or changed.)
When this sequence is reversed, an answer state occurs before the query state. From the answer
state, the reverse computation goes to the query state, provided that the answer state is qyes and the
query word is in the oracle language, or if the answer state is qno and the query word is not in the oracle
language; the reverse computation rejects otherwise. We call this a reverse oracle call. Although a
reverse oracle call does not have the format of an oracle call, it can easily be simulated by an oracle
call and a few more transitions. Hence we have:
Proposition 3.7 Let M be a polynomially balanced polynomial-time injective Turing machine with
NP-oracle. Then M computes a polynomially balanced injective function.
The machine M ′ , obtained by running M in reverse, is equivalent to a polynomial-time injective
Turing machines with NP-oracle, and computes f −1 (where f is the injective function computed by
M ).
✷
Conversely, every injective oracle Turing machine M can be simulated by a reverse injective Turing
machine with the same oracle. Indeed, let M ′ be the reverse of M , and let M1′ be an ordinary injective
oracle machine that simulates M ′ . Finally, let (M1′ )′ be the reverse of M1′ . Then (M1′ )′ is a reverse
injective Turing machine, with the same oracle as M , simulating M .
So, there is no intrinsic difference between injective oracle Turing machines and reverse injective
oracle Turing machines. We could generalize injective Turing machines with oracle so as to allow oracle
calls and reverse oracle calls in the same machine; but by the above discussion, it doesn’t matter much
whether we use oracle calls, reverse oracle calls, or both.
Corollary 3.8

invfP(NP) is an inverse monoid.

Proof. The composite of two polynomially balanced injective functions, computed by polynomial-time
injective Turing machine with NP-oracle, is also polynomially balanced and injective. It is computed
by a polynomial-time injective Turing machine with NP-oracle, obtained by chaining the two machines.
The disjoint union of two sets in NP is in NP; thus the combined machine can use a single NP-oracle
language. Hence, invfP(NP) is a monoid. By Prop. 3.7, invfP(NP) is an inverse monoid. ✷
Remark. Not all functions in fP(NP) have an inverse in fP(NP) (unless the polynomial hierarchy PH
collapses, see Sect. 6 of [3]). Here, fP(NP) denotes the set of polynomially balanced functions computed
by deterministic polynomial-time Turing machines with NP-oracle. But all functions in invfP(NP) have
an inverse in invfP(NP) (by Cor. 3.8).
Proposition 3.9 Suppose f : A∗ → A∗ is an injective and polynomially balanced function such that
both f and f −1 can be computed by deterministic polynomial-time Turing machines with NP-oracle.
Then f can be computed by an injective polynomial-time Turing machine with NP-oracle.
Proof. Bennett’s proof in [1, 2] applies to Turing machines with NP-oracle. An injective Turing
machine for f (with NP-oracle) is obtained by first using the Turing machine for f (on input x), but
with a history tape added (which makes the machine injective). The input x is still present. Once
f (x) has been computed, a copy of it is made on the output tape. The history tape is then used to run
the previous computation in reverse, thus erasing the history tape and the work-tape copy of f (x).
The input x is still on the input tape at this moment, and a copy of f (x) is on the output tape. See
Lemma 1 of [2] (except that now the machine also has an NP-oracle).
To erase x injectively, the Turing machine for f −1 is used on input f (x) (copied from the output
tape). A history tape is added to make the computation injective; x is (re-)computed (while f (x) is
kept on the output tape). Once x has been (re-)computed, the history tape is used to run the previous
9

computation of the f −1 -machine in reverse, thus erasing the history tape, as well as x. A copy of
f (x) is kept as the output tape. See Theorem 2(b) of [2] (except that now the machine also has an
NP-oracle). ✷
We will prove next that invfP(NP) is finitely generated. For this we want to replace all NP-oracles
by one NP-complete set. Moreover, we want the reduction functions to be in invfP.
Recall that for sets L1 , L2 ⊆ A∗ , a many-one reduction from L1 to L2 is a polynomial-time computable function f : A∗ → A∗ such that L1 = f −1 (L2 ); equivalently, (∀x ∈ A∗ )[ x ∈ L1 ⇔ f (x) ∈ L2 ].
A one-one reduction is a many-one reduction f that is injective.
Definition 3.10 For sets L1 , L2 ⊆ A∗ , an invfP-reduction from L1 to L2 is any element f ∈ invfP
such that L1 = f −1 (L2 ).
This definition generalizes the usual many-one reductions in the sense that the elements of invfP are
partial functions (with domain in P). Note that if L1 = f −1 (L2 ) then L1 ⊆ Dom(f ).
By the definition of invfP, if f ∈ invfP then f −1 ∈ invfP, and Im(f ) ∈ P (by Prop. 1.9 in [3], since
f is regular). If f reduces L1 to L2 then f −1 reduces L2 ∩ Im(f ) to L1 . So, unless L2 ⊆ Im(f ), f −1
does not reduce L2 to L1 , and invfP-reducibility is not a symmetric relation.
As we saw in Prop. 3.2, an invfP-reduction can be computed by a polynomially balanced polynomialtime injective Turing machine.
Proposition 3.11 There exists languages that are NP-complete with respect to invfP-reductions.
Proof. An example is the “universal NP-complete language” of Hartmanis [7], defined as follows
(slightly reformulated):
|w|·pw (|x|) :
LNP
univ = {code(w) 11 x 11 0

w is a nondeterministic polynomial-time Turing machine program,
pw is the built-in polynomial of w, and x ∈ Lw }.
In [7] only many-one reductions were considered, but invfP-reductions can be used too. Indeed, for
any language Lv ∈ NP accepted by a nondeterministic polynomial-time Turing machine with program
v, we define the function gv for all x ∈ A∗ by
x 7−→ code(v) 11 x 11 0|v|·pv (|x|) .
Then gv belongs to invfP, since a fixed program v is chosen for the language Lv . And gv is a invfPNP
reduction reduction from Lv to LNP
✷
univ . So, Luniv is complete with respect to invfP-reductions.
Proposition 3.12 The inverse monoid invfP(NP) is finitely generated, as a monoid.
Proof. By Prop. 3.11 there exist sets that are NP-complete with respect to invfP-reductions. Hence,
for all polynomially balanced polynomial-time injective Turing machines with NP-oracle, we can use
a fixed set N as the oracle, where N is NP-complete with respect to invfP-reductions. This changes
the time-complexity of each function in invfP(NP) by a polynomial amount.
Now the proof of Prop. 3.3 goes through if we replace invfP-programs by invfP(NP) -programs. The
latter programs use the three additional states qqu , qyes , and qno , and one instruction for implementing
(N )
a call to the oracle N . We replace injEvq by injEvq , where the latter is computed by an injective
Turing machine that is similar to the one for injEvq , but with oracle calls to N added. ✷
In the next section we will consider inverses and co-inverses that are computed by polynomially
balanced polynomial-time injective Turing machines with NP-oracle.

10

4

Inverses and co-inverses of any element of fP

If P 6= NP then there exist non-regular functions f ∈ fP. In that case we can nevertheless consider the
injective inverses and co-inverses of f in invfP(NP) , as we shall see in Prop. 4.9. First we derive some
general results about injective inverses and co-inverses.

4.1

Inverses, co-inverses, sub-inverses

Here we consider arbitrary functions f, f ′ : A∗ → A∗ , unless more precise conditions are stated. A
subfunction of a function f is, by definition, any function g such that g ⊆ f ; equivalently, Dom(g) ⊆
Dom(f ) and for all x ∈ Dom(g): g(x) = f (x).
Lemma 4.1 If f f ′ f = f then Im(f ) ⊆ Dom(f ′ ).
Proof. If y = f (x) ∈ Im(f ) then f f ′ (y) = f f ′ f (x) = f (x) = y, so f f ′ (y) is defined, hence f ′ (y) is
defined, so y ∈ Dom(f ′ ). ✷
Lemma 4.2.
(1) If f ′ f f ′ = f ′ then Im(f ′ ) ⊆ Dom(f ).
(2) If in addition f ′ is injective, then Dom(f ′ ) ⊆ Im(f ). This does not hold in general when f ′ is
not injective.
Proof. (1) This is equivalent to Lemma 4.1, up to notation.
(2) If z ∈ Dom(f ′ ) then f ′ (z) = f ′ f f ′ (z) is defined, hence f f ′ (z) is defined and f f ′ (z) ∈ Im(f ).
When f ′ is injective we can consider its set-theoretic inverse f ′−1 , and we have f ′−1 f ′ = idDom(f ′ ) .
Applying f ′−1 on the left to f ′ (z) = f ′ f f ′ (z) yields idDom(f ′ ) ◦ f ′ f (z) = z (if z ∈ Dom(f ′ )). Hence
idDom(f ′ ) ◦ f f ′ (z) is defined, and idDom(f ′ ) ◦ f f ′ (z) = f f ′ (z) = z, so z ∈ Im(f ).
When f ′ is not injective, the result might not hold. Consider for example f = {(a, b)} and
′
f = {(a, a), (b, a)}. Then f ′ f f ′ = f ′ (and f f ′f = f as well, so f and f ′ are mutual inverses); but
Dom(f ′ ) = {a, b} 6⊆ {b} = Im(f ). ✷
Corollary 4.3 If f, f ′ are mutual inverses and f ′ is injective then Dom(f ′ ) = Im(f ). This does not
hold in general when f ′ is not injective.
✷
Lemma 4.4 If f ′ f f ′ = f ′ and f ′ is injective, then f ′−1 = f |Im(f ′ ) ; equivalently,
−1
f ′ = f |Im(f ′ )
= f −1 ∩ Dom(f ′ ) × Im(f ′ ).

Hence, f ′−1 ⊆ f .

Proof. Applying f ′−1 on the left and the right to f ′ = f ′ f f ′ yields idDom(f ′ ) ◦ f ◦ idIm(f ′ ) = f ′−1 . This
is equivalent to f |Im(f ′ ) ∩ f −1 (Dom(f ′ )) = f ′−1 . Hence, f ′−1 ⊆ f , so f ′ = (f ′−1 )−1 ⊆ f −1 , where f −1 =
{(y, x) : y = f (x)}. Thus, Im(f ′ ) = f ′ (Dom(f ′ )) ⊆ f −1 (Dom(f ′ )), hence Im(f ′ ) ∩ f −1 (Dom(f ′ )) =
Im(f ′ ); so f |Im(f ′ ) ∩ f −1 (Dom(f ′ )) = f |Im(f ′ ) = f ′−1 .
The equality f ′ = f −1 ∩ Dom(f ′ ) × Im(f ′ ) is just a logical reformulation of f ′ = (f |Im(f ′ ) )−1 . ✷
Corollary 4.5 If f ′ is an injective co-inverse of f , then f ′ is a mutual inverse of f |Im(f ′ ) (which is an
injective subfunction of f ). Moreover, f ′ is uniquely determined by f and Im(f ′ ), as f ′ = (f |Im(f ′ ) )−1 .
Proof. Since f ′ = idIm(f ′ ) ◦ f ′ , we have f ′ = f ′ f f ′ = f ′ ◦ f ◦ idIm(f ′ ) ◦ f ′ = f ′ ◦ f |Im(f ′ ) ◦ f ′ . Moreover,
since f |Im(f ′ ) = f ′−1 (by Lemma 4.4), we have f |Im(f ′ ) = f ′−1 = f ′−1 f ′ f ′−1 = f |Im(f ′ ) ◦ f ′ ◦ f |Im(f ′ ) .
✷
Corollary 4.6 If f ′ f f ′ = f ′ and Dom(f ′ ) = Im(f ), then f ′ is an injective mutual inverse of f .
11

Proof. When Dom(f ′ ) = Im(f ) then Im(f ′ ) is a choice set of f . Indeed, for every y ∈ Im(f ), f ′ (y)
is defined and f ′ (y) ∈ f −1 (y) (since f ′ ⊂ f −1 by the second equality in Lemma 4.4). Hence f ′ is an
inverse of f . Injectiveness follows from the observations made in the Introduction and at the beginning
of Section 2. ✷
Theorem 4.7 (anti-homomorphic property of co-inverses).
Suppose fi′ is an injective co-inverse of fi for i = 1, 2. Then f1′ f2′ is an injective co-inverse of f2 f1 .
Proof. We first observe that for subidentities idX , idY , we have idX idY = idX∩Y = idY idX . Since fi′
is injective, fi′ fi′−1 = idIm(fi′ ) , and fi′−1 fi′ = idDom(fi′ ) . Hence
f1′ f2′ f2′−1 f1′−1 f1′ f2′ = f1′ idIm(f2′ ) idDom(f1′ ) f2′ = f1′ idDom(f1′ ) idIm(f2′ ) f2′ = f1′ f2′ .
So, f1′ f2′ = f1′ f2′ f2′−1 f1′−1 f1′ f2′ ⊆ f1′ f2′ f2 f1 f1′ f2′ (by Lemma 4.4). Now, since f1′ f2′ ⊆ f1′ f2′ f2 f1 f1′ f2′ ,
we have f1′ f2′ (x) = f1′ f2′ f2 f1 f1′ f2′ (x) when f1′ f2′ (x) is defined. And when f1′ f2′ (x) is not defined,
f1′ f2′ f2 f1 f1′ f2′ (x) is not defined either. Thus, f1′ f2′ = f1′ f2′ f2 f1 f1′ f2′ . ✷
Remark. Theorem 4.7, though straightforward, is remarkable as it applies to injective co-inverses
but not to injective inverses or mutual inverses.
The latter can be illustrated by the following example: Let f1 = {(0, 0), (1, 0)} = f2 , and let
f1′ = {(0, 1)} = f2′ , so fi and fi′ are mutual inverses (i = 1, 2), and fi′ is injective. But f1′ ◦ f2′ = θ (the
empty map), which is not an inverse of f2 f1 = {(0, 0), (1, 0)}.
In [3] (Prop. 6.1) we showed that every element f ∈ fP has an inverse in fP(NP) ; one such inverse
′ , defined by
is fmin

min(f −1 (y))
if y ∈ Im(f ),
′
fmin (y) =
undefined
otherwise,
where the min operation is taken with respect to the length-lexicographic order, ≤llex , of {0, 1}∗ . Recall
that by definition, u ≤llex v iff |u| < |v| or [ |u| = |v| and u ≤dict v ]; here, ≤dict is the dictionary order
of {0, 1}∗ determined by 0 <dict 1.
Proposition 4.8 For every f ∈ fP we have:
′
′
′
′
′ ;
(1) f ◦ fmin
= idIm(f ) ; hence, f ◦ fmin
◦ f = f ; also fmin
◦ f ◦ fmin
= fmin
′ ) ∈ coNP;
(3) Im(fmin

′ ) = Im(f ) ∈ NP;
(4) Dom(fmin

′
(2) fmin
is injective;

′−1
∈ fP(NP) .
(5) fmin

′ .
Proof. (1) is obvious from the definition of fmin
′
(2) Injectiveness of fmin
follows from the fact that the sets f −1 (y) (for y ∈ Im(f )) are two-by-two
disjoint.
′ ) iff x ∈ Dom(f ) and (∀z)[ z <
(3) We have: x ∈ Im(fmin
llex x ⇒ f (z) 6= f (x) ] (the latter sentence
expresses that x is the ≤llex -minimum element in its modf -class). Since Dom(f ) ∈ P, since the relation
{(z, x) : z <llex x ⇒ f (z) 6= f (x)} is in P, and since this relation is universally quantified (by
′ ) ∈ coNP.
(∀z, z <llex x)), it follows that Im(fmin
′
′ ) = Im(f ). And Im(f ) ∈ NP for every f ∈ fP.
(4) By the definition of fmin
we have Dom(fmin
′−1
′−1
(NP)
′ ) (by Lemma 4.4), and f ∈ fP,
= f |Im(fmin
. Indeed, fmin
(5) As a consequence of (2), fmin ∈ fP
′−1
′
and Im(fmin ) ∈ coNP, so fmin is computed by any Turing machine for f with an added oracle call to
′ ).
Im(fmin
✷
′
In the proof of Prop. 6.1 in [3] we showed that fmin
∈ fP(NP) . Next we strengthen this by showing
′
that the oracle Turing machine that computes fmin is an injective Turing machine with an NP-oracle. In
Def. 3.6 we introduced the set invfP(NP) of polynomially balanced functions computed by polynomialtime injective Turing machines with an NP-oracle.

Proposition 4.9 Every f ∈ fP has an inverse f ′ in invfP(NP) (hence f ′−1 ∈ invfP(NP) ), with the
additional property that Im(f ′ ) ∈ coNP.
12

′ , which is injective as we just saw, hence f ′−1 is an injective function. Both f ′
Proof. Let f ′ be fmin
(NP)
and f ′−1 are in fP
; this holds for f ′ by Prop. 6.1 in [3], and for f ′−1 by Prop. 4.8. Hence by Prop.
(NP)
′
3.9, f ∈ invfP
.
Since f ′ is computed by an injective Turing machine (with oracle), f ′−1 can be computed by the
same machine run backwards; so f ′−1 ∈ invfP(NP) .
′ ) ∈ coNP.
We proved in Prop. 4.9 that Im(fmin
✷
′ (y) in
Remark. As an alternative proof of Prop. 4.9, observe that the algorithm for computing fmin
the proof of Prop. 6.1 in [3] actually describes an injective Turing machine; it makes oracle calls to
the set {(z, u) : z ∈ f (uA∗ )} (which is in NP for any fixed f ∈ fP).

Based on the anti-homomorphic property of co-inverses (Theorem 4.7) we define:
Definition 4.10 The monoid of co-inverses of fP is
cofP = {f ′ ∈ invfP(NP) : f ′ is a co-inverse of some element of fP}.
Equivalently, an element f ′ of invfP(NP) belongs to cofP iff f ′ has an inverse in fP.
By Theorem 4.7, cofP is indeed a monoid.
′
′
Also, fmin
∈ cofP for every f ∈ fP, since f is a mutual inverse of fmin
(Prop. 4.8). Hence, for every
f ∈ fP, cofP contains a mutual inverse of f .
One could also consider the monoid of inverses of fP, namely {g ∈ invfP(NP) : g is an inverse of
some element of fP}. However, this is just all of invfP(NP) , since every element of invfP(NP) is an inverse
of the empty map θ ∈ fP. So, being an inverse of an element in fP is a trivial notion; but having an
inverse in fP (i.e., being a co-inverse of an element in fP) is non-trivial. The question whether cofP is
equal to invfP(NP) has an interesting “answer”, which is presented in Prop. 4.20 below.
Proposition 4.11

cofP ∩ fP = invfP.

Proof. [⊇] If f ′ ∈ invfP then f ′−1 ∈ invfP ⊆ fP. Moreover, f ′ f ′−1 f ′ = f ′ , so f ′ is a co-inverse of an
element in fP. Hence f ′ ∈ cofP.
[⊆] If f ′ ∈ cofP ∩ fP then there exists f ∈ fP such that f ′ f f ′ = f ′ , hence f ′ is a regular element of
fP. Since we assume f ′ ∈ cofP, it follows that f ′ is injective. So, f ′ is an injective regular element of
fP, i.e., f ′ ∈ invfP. ✷
On the other hand, invfP(NP) ∩ fP contains all injective one-way functions. In fact, invfP(NP) ∩ fP =
invfP iff injective one-way functions do not exist. The latter is the case iff P = UP (see e.g. section
12.1 in [13]). But cofP contains no one-way function, since every element of cofP has an inverse in fP.
Definition 4.12 Let injfP denote the monoid of all injective functions in fP.
The set of regular elements of injfP is exactly the submonoid invfP (by the definition of invfP), hence
the set of injective one-way functions (for worst-case complexity, see Prop. 1.3) is injfP − invfP. We
saw that invfP and invfP(NP) are regular monoids (in fact, inverse monoids). On the other hand, injfP
is regular iff injective one-way functions do not exist. Thus we have:
injective one-way functions exist iff invfP 6= injfP 6= invfP(NP) .
Since invfP consists of the regular elements of injfP, we also have:
injective one-way functions exist iff invfP 6= injfP.
Since invfP(NP) is regular we have,
if injective one-way functions exist, then injfP 6= invfP(NP) .
We will also see (Theorem 4.18) that one-way functions exist iff invfP 6= invfP(NP) .
We saw that cofP contains no one-way functions (see the observations after Prop. 4.11), so we
have: injfP ∩ cofP = invfP. Moreover:
13

Proposition 4.13 invfP(NP) ∩ fP = injfP.
Proof. [⊆] Every f ∈ invfP(NP) is injective, so the inclusion ⊆ holds.
′
[⊇] If f ∈ injfP then fmin
= f −1 ∈ invfP(NP) , by Prop. 4.9. It follows that (f −1 )−1 = f ∈ invfP(NP) ,
by Prop. 3.7. Hence f ∈ invfP(NP) ∩ injfP ⊆ invfP(NP) ∩ fP. ✷
✬

✬

invfP(NP)

injfP
✩
✩

✬

cofP

✫

✩ fP

✩

✫

invfP
✫

✪
✪

✪

✪

Figure 1: Relations between fP, invfP(NP) , cofP, invfP, and injfP.

There is an interesting connection between co-inverses and sub-inverses of f .
Definition 4.14 A function g′ is a sub-inverse of a function f iff there exists g ⊆ f such that
gg′ g = g and g ′ gg′ = g ′ . I.e., the sub-inverses of f are the mutual inverses of the subfunctions of f .
Proposition 4.15 For any function f : A∗ → A∗ , the injective co-inverses of f are the same as the
injective sub-inverses of f .
Proof. [⇒] Let f ′ be an injective co-inverse of f ; then Dom(f ′ ) ⊆ Im(f ) and Im(f ′ ) ⊆ Dom(f ), by
Lemmas 4.1 and 4.2. Let us consider the following restriction of f : g = f |Im(f ′ ) . We claim that f ′ is
a mutual inverse of g, hence f ′ is a sub-inverse of f . Recall that f ′ = (f |Im(f ′ ) )−1 , by Lemma 4.4. It
follows from this that gf ′ g = f |Im(f ′ ) ◦ (f |Im(f ′ ) )−1 ◦ f |Im(f ′ ) = f |Im(f ′ ) = g; similarly it follows that
f ′ gf ′ = (f |Im(f ′ ) )−1 ◦ f |Im(f ′ ) ◦ (f |Im(f ′ ) )−1 = (f |Im(f ′ ) )−1 = f ′ .
So, f ′ is an injective sub-inverses of f .
[⇐] Let g ⊂ f be any restriction of f , and let g′ be any injective mutual inverse of g; in other words,
g′ is an injective sub-inverse of f . We claim that g ′ is a co-inverse of f .
By Corollary 4.3, and Lemma 4.4, we have: Dom(f ′ ) = Im(f ), and g′ = (g|Im(g′ ) )−1 . Since g ⊂ f
the latter implies g ′ = (f |Im(f ′ ) )−1 . Hence, g′ f g′ = (f |Im(f ′ ) )−1 ◦ f ◦ (f |Im(f ′ ) )−1 = (f |Im(f ′ ) )−1 = g′ .
So, g ′ is a co-inverse of f . ✷
Note that in part [⇐] of the above proof, g need not be injective, but g|Im(g′ ) = f |Im(g′ ) is injective.
Thus we have:

14

If g′ is an injective sub-inverse of f and it is a mutual inverse of a subfunction of f , then g ′ is
also a mutual inverse of an injective subfunction of f .
The following gives a relation between two notions of sub-inverse. We defined a sub-inverse of f to be
a mutual inverse of a subfunction of f (Def. 4.14). We could, instead, have defined a sub-inverse of f
to be a subfunction of a mutual inverse of f .
Proposition 4.16.
(1) If g′ is a subfunction of a mutual inverse of f , then g ′ is a sub-inverse of f . (For this fact, g′
need not be injective, and f need not be in fP.)
(2) If g′ ∈ invfP(NP) is a sub-inverse of f ∈ fP, then g ′ is a subfunction of some mutual inverse
f ′ ∈ invfP(NP) of f .
Proof. (1) Let g ′ ⊆ f ′ with f f ′ f = f and f ′ f f ′ = f ′ . Let g = f g′ f ; then g ⊆ f f ′ f = f . And for
all x ∈ Dom(g) we have gg ′ g(x) = f f ′ f (x) = f (x) = g(x) (the latter since x ∈ Dom(g)). So gg ′ g = g.
Moreover, for all y ∈ Dom(g′ ) we have g′ gg ′ (y) = f ′ f f ′ (y), since g′ ⊆ f ′ and g ⊆ f ; and f ′ f f ′ (y) = y.
So, g ′ gg ′ = g′ .
(2) Since g ′ ∈ invfP(NP) , g ′ is injective, hence it is an injective co-inverse of f (by Prop. 4.15).
Hence, g′ = (f |Im(g′ ) )−1 , and g ′ is a mutual inverse of g = f |Im(g′ ) ⊆ f . We can extend g ′ to the
following mutual inverse of f : For all y ∈ Im(f ) let
 ′
g (y)
if y ∈ Dom(g′ ),
′
f (y) =
′
fmin (y)
otherwise.
′
′ (y ) for
It follows that f ′ is injective. Indeed, both g′ and fmin
are injective. Moreover, g′ (y1 ) 6= fmin
2
′ (y ); but
all y1 ∈ Dom(g′ ) and all y2 ∈ Im(f ) − Dom(g ′ ), since if we had equality then f g′ (y1 ) = f fmin
2
′ (y ) = y ; so we would have y = y , but y ∈ Dom(g ′ )
f g′ (y1 ) = y1 since g′ = (f |Im(g′ ) )−1 , and f fmin
2
2
1
2
1
′
and y2 6∈ Dom(g ).
Also, f ′ is clearly a mutual inverse of f .
′ , there is an
Since g′ is computed by a injective Turing machine with NP-oracle, and likewise fmin
injective Turing machine with NP-oracle for f ′ ; the Turing machine for g′ , being deterministic, can
check whether g′ (y) is defined, i.e., whether y ∈ Dom(g′ ). Hence, f ′ ∈ invfP(NP) . ✷

4.2

Connections with NP

The next theorem motivates the study of the monoid cofP (and of invfP) in the context of the P versus
NP problem. We prove an easy Lemma first.
Lemma 4.17 Let f, h be functions A∗ → A∗ and let Z ⊂ A∗ . If f ◦ h|Z ◦ f = f , then f hf = f .
Proof. For x 6∈ Dom(f ), f hf (x) and f (x) are both undefined. For x ∈ Dom(f ), h|Z (f (x)) is defined,
otherwise f ◦ h|Z ◦ f (x) would be undefined, and thus would not be equal to f (x). Hence we have
f (x) ∈ Z, so Im(f ) ⊆ Z. It follows that h|Z (f (x)) = h(f (x)), for all x ∈ Dom(f ). Hence h|Z ◦f = h◦f ,
thus f ◦ h|Z ◦ f = f h f = f . ✷
Theorem 4.18 The following are equivalent:
P = NP;
cofP = invfP;
cofP ⊂ fP;
cofP is regular;
invfP(NP) = invfP.

15

Proof. We use the following logical fact: If X ⇒ Yi and X ⇒ Y i , then X ⇔ Yi (for i = 1, 2, . . . ).
Here, “P = NP” plays the role of X.
[⇒] We assume P = NP. We obviously have invfP ⊆ cofP. If P = NP then fP(NP) = fP, hence
cofP ⊆ fP. Also, fP is regular when P = NP. Since all elements of cofP are injective, all elements of
cofP are injective regular elements of fP, i.e., cofP ⊆ invfP. In conclusion, cofP = invfP.
If cofP = invfP then cofP ⊂ fP. The inclusion is strict because fP has some non-injective elements.
And if cofP = invfP then, since invfP is regular, cofP is regular.
[⇐] If P 6= NP then there exists f ∈ fP such that f is not regular. For f there exists a mutual inverse
f ′ ∈ invfP(NP) such that Dom(f ′ ) = Im(f ); hence, f ′ ∈ cofP. Moreover, Dom(f ′ ) = Im(f ) ∈ NP; and f ′
′
can be chosen so that in addition, Im(f ′ ) ∈ coNP (e.g., by choosing f ′ = fmin
as in Prop. 4.9). Hence,
(NP)
′−1
′−1
′
′
f
∈ invfP
(since f
= f |Im(f ′ ) and Im(f ) ∈ coNP). However, f 6∈ fP, since f is not regular
in fP.
Let us assume by contradiction that the monoid cofP is regular. Then f ′ (as above) is a regular element of cofP, hence (by Lemma 4.9), f ′−1 ∈ cofP. This implies (by the definition of cofP)
that f ′−1 h f ′−1 = f ′−1 for some h ∈ fP. Composing on the left and on the right with f ′ yields
idIm(f ′ ) h idDom(f ′ ) = f ′ ; equivalently, h|Dom(f ′ ) ∩ h−1 (Im(f ′ )) = f ′ . Hence, f f ′ f = f h|Dom(f ′ ) ∩ h−1 (Im(f ′ )) f
= f . It follows (by Lemma 4.17) that h is an inverse of f , since the restriction h|Dom(f ′ ) ∩ h−1 (Im(f ′ )) is
an inverse of f . Hence (since f is not regular), h 6∈ fP; but this contradicts the previous assumption
that h ∈ fP. Thus cofP is not regular.
Since the monoid invfP is regular, we conclude that cofP 6= invfP.
And cofP 6= invfP implies cofP 6⊂ fP; indeed, if we had cofP ⊂ fP then we would have cofP =
cofP ∩ fP = invfP.
Finally, if invfP(NP) = invfP then cofP = invfP, hence by what we proved above, P = NP. Conversely, if P = NP then every polynomial-time injective Turing machine with NP-oracle is equivalent
to a polynomial-time deterministic Turing machine (without oracle). Thus if f ∈ invfP(NP) (hence by
Prop. 3.7, f −1 ∈ invfP(NP) ), then f, f −1 ∈ fP. By Bennett’s results [1, 2] (especially Lemma 1 and
Theorem 2 (b) in [2]), this implies f ∈ invfP. ✷
Although every element of cofP has an inverse in fP (by the definition of cofP), not every element
of cofP has an inverse in cofP, unless P = NP; the latter follows from the fact that cofP is regular iff
P = NP.
By definition, cofP ⊆ invfP(NP) . We will now address the question whether this inclusion is strict;
it turns out, interestingly, that this is equivalent to the question whether P 6= NP.
Lemma 4.19 Let f ∈ fP, and let f ′ ∈ cofP be a co-inverse of f such that Im(f ′ ) ∈ coNP. Then
f ′−1 ∈ fP(NP) .
For every f ∈ fP there exists a co-inverse f ′ ∈ cofP of f such that Im(f ′ ) ∈ coNP and Dom(f ′ ) ∈
NP.
Proof. Since f ∈ fP and Im(f ′ ) ∈ coNP, f ′−1 = f |Im(f ′ ) can be computed by a Turing machine for f
with NP-oracle Im(f ′ ).
We saw above (and in [3]) that for every f ∈ fP there exists a mutual inverse (hence a co-inverse)
′ .
f ′ for which Im(f ′ ) ∈ coNP and Dom(f ′ ) ∈ NP; e.g., let f ′ = fmin
✷
Proposition 4.20 P 6= NP iff cofP 6= invfP(NP) .
In any case (i.e., whether P 6= NP or not), cofP and invfP(NP) have the same set of idempotents.
Proof. [⇐] If cofP = invfP(NP) , then for every f ′ ∈ invfP(NP) there exists f ∈ fP such that f ′ f f ′ = f ′ .
By Lemma 4.4, f ′−1 ⊆ f , and by Lemma 4.19, f ′−1 ∈ invfP(NP) . It follows that f ′ has an injective
inverse f ′−1 ∈ invfP(NP) , i.e., f ′ is regular in cofP = invfP(NP) . This holds for all f ′ ∈ cofP, hence cofP
is regular. Thus by Theorem 4.18, P = NP.
16

[⇒] If P = NP then cofP = invfP, which in this case is also equal to invfP = invfP(NP) .
If e is an idempotent of invfP(NP) then e is also a co-inverse of an element of fP; indeed, e ◦ idA∗ ◦ e =
e. Hence e ∈ cofP. ✷
Proposition 4.21

P 6= NP iff cofP contains regular elements that do not belong to invfP.

Proof. [⇐] If P = NP then cofP = invfP (by Theorem 4.18), so there are no (regular) elements in
cofP that are not in invfP.
[⇒] If P 6= NP then we construct the following example of a regular element in cofP that does not
belong to invfP. Let L ⊂ A∗ be a coNP-complete set. Then idL ∈ invfP(NP) and it is regular (being an
idempotent). Also, idL = idL ◦idA∗ ◦idL , hence idL is a co-inverse of an element of fP. Thus, idL ∈ cofP.
But if P 6= NP then idL 6∈ invfP, since L is coNP-complete. ✷
We saw that invfP and invfP(NP) are finitely generated. Hence, if cofP were not finitely generated,
this would imply that cofP 6= invfP, which would imply that P 6= NP (by Theorem 4.18). However, we
will prove next that cofP is finitely generated.
We will first show that cofP has a machine (or program) model, and that there is a corresponding
evaluation function for all bounded-complexity functions in cofP. This is similar to the situation in fP,
invfP, and invfP(NP) .
A cofP-program is of the form (v ′ , w), where v ′ is any invfP(NP) -program (with built-in timecomplexity and balance function), and w is any fP-program (with built-in time-complexity and balance
function). An invfP(NP) -program describes a polynomially balanced polynomial-time injective Turing
machine, with a fixed NP-oracle N (where N is NP-complete). The functions in fP or invfP(NP) specified
by programs w or v ′ are denoted by φw , respectively ψv′ . On input y ∈ A∗ , the program (v ′ , w) is
evaluated as follows:
(1)
(2)
(3)

x = ψv′ (y) is computed;
φw (x) is computed;
if φw ◦ ψv′ ◦ φw (x) = φw (x) and ψv′ ◦ φw ◦ ψv′ (y) = ψv′ (y) then the output is ψv′ (y);
there is no output otherwise.

The function specified by program (v ′ , w) on input y is denoted by Φ(v′ ,w) . It is easy to see that Φ(v′ ,w)
is a subinverse of φw , and a subfunction of ψv′ . Thus, Φ(v′ ,w) ∈ cofP.
Conversely, every function h ∈ cofP has an invfP(NP) -program, say v ′ ; and h has an inverse φw ∈ fP
for some fP-program w. Then (v ′ , w) is a cofP-program for h.
Based on the cofP-programs and a polynomial bound q, we can construct an evaluation function
(N )
(N )
evCoq such that evCoq (code(v ′ ) 11 code(w) 11 y) = code(v ′ ) 11 code(w) 11 Φ(v′ ,w) (y), for y and
(v ′ , w) as above. This is similar to Section 3.2.
Theorem 4.22 The monoid cofP is finitely generated.
Proof. The proof is the same as for invfP(NP) (Prop. 3.12), except that evCoq (with programs (v ′ , w)
(N )
as above) is used instead of injEvq . ✷
We saw that P 6= NP iff cofP is not regular. The set of elements of cofP that are regular in cofP will
be denoted by RegcofP. We will see that it has interesting properties.
Proposition 4.23 (1) The set RegcofP is a finitely generated inverse submonoid of cofP.
(2) If P 6= NP then invfP $ RegcofP $ cofP $ invfP(NP) . If P = NP then invfP = invfP(NP) .
(3) An element f ∈ fP has an inverse in RegcofP iff f is regular in fP.

17

Proof. (1) For any g ∈ RegcofP, let g′ ∈ RegcofP be a mutual inverse of g. Multiplying gg′ g = g
on the left and the right by g−1 we obtain: idDom(g) ◦ g′ ◦ idIm(g) = g−1 . Hence g−1 ∈ cofP, being a
product of elements of cofP (since the idempotents idDom(g) , idIm(g) belong to cofP). Thus we proved:
For all g ∈ RegcofP : g −1 ∈ cofP.
For any g1 , g2 ∈ RegcofP we have therefore, g1−1 , g2−1 ∈ cofP, hence g2 g1 has g1−1 g2−1 ∈ cofP as an
inverse, so g2 g1 is regular in cofP. This proves that RegcofP is closed under composition. Also, since
all elements of RegcofP are injective, RegcofP is an inverse monoid.
The proof of finite generation of RegcofP is similar to the proof of finite generation of cofP. We
construct an evaluation function for the elements of RegcofP, based on the following machine (or
program) model for the elements of RegcofP. A RegcofP-program is any pair (u, v ′ ) of cofP-programs,
and the function Φ(u,v′ ) computed by this program is defined by
Φ(u,v′ ) (x) = ψu (x)

if

ψu ψv′ ψu (x) = ψu (x);

and Φ(u,v′ ) (x) is undefined otherwise. Since the relation ψu ψv′ ψu (x) = ψu (x) can be checked in P(NP) ,
Φ(u,v′ ) belongs to invfP(NP) . And since ψu ∈ cofP has some inverse f ∈ fP, and Φ(u,v′ ) is a subfunction
of ψu , Φ(u,v′ ) also has f as an inverse; hence, Φ(u,v′ ) ∈ cofP. Moreover, since ψu ψv′ ψu (x) = ψu (x) for
every x ∈ Dom(Φ(u,v′ ) ), and Φ(u,v′ ) ⊆ ψu , we have Φ(u,v′ ) ψv′ Φ(u,v′ ) = Φ(u,v′ ) . So Φ(u,v′ ) is regular in
cofP. Finally, every regular element of cofP obviously has a program of the form (u, v ′ ) as above.
The rest of the proof of finite generation is very similar to the one for cofP.
(2) The second part of (2) was already proved in Theorem 4.18. On the other hand, if P 6= NP then
cofP is not regular (by Theorem 4.18), so RegcofP 6= cofP 6= invfP(NP) . Also, cofP contains regular
elements that are not in invfP, by Prop. 4.21, hence invfP 6= RegcofP.
(3) If f is a regular element of fP then f has an inverse in invfP, by Coroll. 2.3.
In general, let f be an element in fP that has an inverse f ′ ∈ RegcofP; we want to show that f is
regular in fP. By what we proved in (1) of the present proof, f ′−1 ∈ cofP. We have f ′−1 gf ′−1 = f ′−1 for
some g ∈ fP, since f ′−1 ∈ cofP. Multiplying this on the left and the right by f ′ yields idI ◦ g ◦ idD = f ′ ,
where D = Dom(f ′ ) and I = Im(f ′ ). Since f ′ is an inverse of f , Lemma 4.17 implies that g is an
inverse of f . Since g ∈ fP, it follows that f is regular in fP. ✷
We saw that the monoids fP, invfP, invfP(NP) , and cofP are finitely generated. For injfP we ask
similarly:
Question: Is injfP finitely generated?
We do not know the answer. If we could show that injfP is not finitely generated, then this would
prove that injfP 6= invfP, i.e., injective one-way functions exist, hence P 6= UP, and hence P 6= NP.
When we proved that fP, invfP, invfP(NP) , and cofP are finitely generated, we used machine (or
program) models, and evaluation functions. It seems that injfP does not have a program model, since
injectiveness is a for-all property, that does not have finite witnesses in general. To illustrate the
difficulty of finding a program model for injfP, here is an idea that does not work. We saw that
injfP = fP ∩ invfP(NP) , and this suggests that a function in injfP can be specified by a pair (u, w), where
w is an fP-program (for φw ∈ fP), and u is an invfP(NP) -program (for ψu ∈ invfP(NP) ); the program
(u, w) specifies the injective function ψu ∩ φw . But ψu ∩ φw ranges over all of invfP(NP) and does
not necessarily belong to injfP (unless injfP = invfP(NP) , which would imply that P = NP). So, this
approach towards proving finite generation does not work (unless one also proves that P = NP). It
seems that injfP is not finitely generated (but this will probably be very difficult to prove).

5

Subgroups and group-inverses

We first characterize the maximal subgroups of invfP, cofP, and invfP(NP) . Then we consider elements
of fP that have an inverse in such a subgroup (i.e., a group-inverse). Typically, elements of fP do not

18

have a group-inverse, but we will see that all elements of fP are reduction-equivalent to elements that
have group-inverses.

5.1

Maximal subgroups

We first characterize the idempotents of injfP.
Proposition 5.1 For any f ∈ injfP we have: f is an idempotent iff f = idZ for some set Z ⊆ A∗
with Z ∈ P. Hence injfP and invfP have the same idempotents.
Proof. If f ∈ injfP and f = f ◦ f , then we compose on the left with f −1 (which exists, since f is
injective, but f −1 might not belong to injfP); this yields idD = idD ◦ f , where D = Dom(f ). Hence for
all x ∈ D = Dom(f ) we have x = f (x). Thus, f = idD . Since f ∈ fP, D = Dom(f ) ∈ P.
Conversely, if Z ∈ P then idZ can be computed by a deterministic polynomial-time Turing machine.
Moreover, idZ ∈ invfP since idZ is injective, and it is regular (being an idempotent). ✷
Proposition 5.2 The maximal subgroup of invfP and injfP are the same.
Let idZ be an idempotent of invfP. The maximal subgroup of invfP with identity idZ consists of
the permutations of Z that belong to invfP. In particular, the group of units of invfP consists of all
permutations of A∗ that belong to invfP.
Proof. If f belongs to a subgroup of injfP then f is regular, hence f ∈ invfP.
Obviously, the permutations in invfP with domain and image Z form a subgroup of invfP. Conversely, if f ∈ invfP belongs to the maximal subgroup with identity idZ , then f −1 f = f f −1 = idZ ; so
the domain and the image of f are both Z. Since f ∈ invfP, f is injective, and f −1 ∈ invfP. Hence f
permutes Z. ✷
Proposition 5.3 Every maximal subgroup of invfP is also a maximal subgroup of fP. The group of
units of fP is the same as the group of units of invfP.
Proof. A maximal subgroup of fP is a regular H-class. For fP the characterization of the L- and the
R-relation (see Prop. 2.1 in [3]) implies that every element f of a maximal subgroup of fP with unit
idZ satisfies Im(f ) = Z = Dom(f ) and f is injective (since f has the same partition as idZ ). Thus f
belongs to invfP. ✷
The converse of Prop. 5.3 is of course not true; e.g., fP contains non-injective idempotents, hence
subgroups that are not contained in invfP.
Let us now look at the idempotents and subgroups of invfP(NP) and of cofP. We saw that invfP(NP)
and cofP have the same idempotents (Prop. 4.20). And we saw that invfP(NP) is an inverse monoid
(Cor. 3.8); on the other hand, cofP is not regular, unless P = NP (by Theorem 4.18).
Lemma 5.4 For every L ⊂ A∗ we have: L ∈ P(NP) iff idL ∈ invfP(NP) .
Proof. [⇒] If L ∈ P(NP) then idL can be computed by deterministic polynomial-time Turing machine
with NP-oracle. Moreover, the inverse of idL (which is just idL itself) also has that property, hence
by Prop. 3.9, idL can be computed by an injective polynomial-time Turing machine with NP-oracle.
Hence, by the definition of invfP(NP) we have idL ∈ invfP(NP) .
[⇐] From a polynomial-time injective Turing machine with NP-oracle, computing idL , one immediately obtains a deterministic polynomial-time Turing machine with NP-oracle, accepting L. ✷
Proposition 5.5 Every idempotent of invfP(NP) (and cofP) is of the form idL , where L ∈ P(NP) ,
L ⊆ A∗ . Moreover, every L ∈ P(NP) is accepted by an injective polynomial-time Turing machine with
NP-oracle.
19

Proof. Let f = f ◦f be an idempotent of invfP(NP) . Multiplying in the left by f −1 yields idD = idD ◦f ,
where D = Dom(f ). Hence, f = idD . Since f ∈ invfP(NP) we have D ∈ P(NP) (by Lemma 5.4).
Conversely, if Z ∈ P(NP) then idZ ∈ invfP(NP) (by Lemma 5.4). From this we obtain an injective
polynomial-time Turing machine with NP-oracle, accepting Z. ✷
Proposition 5.6 (1) The maximal subgroup of invfP(NP) with idempotent idL (where L ∈ P(NP) )
consists of all the permutations of L that belong to invfP(NP) . In particular, the group of units of
invfP(NP) consists of all permutations of A∗ that belong to invfP(NP) .
(2) The maximal subgroup of cofP with idempotent idL (where L ∈ P(NP) ) consists of all permutations
g of L such that g = f ∩ (L × L) and g −1 = h ∩ (L × L) for some f, h ∈ fP.
Hence, if L ∈ P then the maximal subgroup of cofP with idempotent idL is a subgroup of invfP. In
particular, the group of units of cofP is the same as the group of units of invfP.
Proof. (1) By injectiveness of the elements of invfP(NP) , every element of the maximal subgroup
of invfP(NP) with idempotent idL is a permutation of L. Moreover, for every g ∈ invfP(NP) we have
g−1 ∈ invfP(NP) (by Prop. 3.7); hence the permutations of L in invfP(NP) form a subgroup of invfP(NP) .
(2) If g ∈ invfP(NP) belongs to a maximal subgroup of cofP with idempotent idL , then both g and
g−1 are permutations of L. If g has an inverse h ∈ fP then multiplying ghg = g on the left and on the
right by g−1 yields idL ◦ h ◦ idL = g −1 ; moreover, idL ◦ h ◦ idL = h ∩ (L × L). Similarly, for g−1 ∈ coP
we obtain f ∩ (L × L) = g for some f ∈ fP.
Conversely, let g be a permutation of L ∈ P(NP) such that g = f ∩ (L × L) and g−1 = h ∩ (L × L)
for some f, h ∈ fP. Then g, g −1 belong to invfP(NP) since L ∈ P(NP) and f, h ∈ fP. Moreover, g and
g−1 belong to cofP; indeed, the inverses f ∩ (L × L) and h ∩ (L × L) can be extended to inverses h,
respectively f , in fP (by Lemma 4.17). Since g is a permutation of L, it follows now that g belongs to
a subgroup of cofP. ✷
We saw in Prop. 4.21 that unless P = NP, cofP contains regular elements that are not in invfP.
The next Proposition describes the regular elements of cofP.
Proposition 5.7 Every element of cofP that is regular in cofP has the form f ∩ (K × H), for some
f ∈ fP and K, H ∈ P(NP) .
Conversely, suppose f, h ∈ fP and K, H ∈ P(NP) are such that f ∩ (K × H) and h ∩ (H × K) are
injective and mutual inverses. Then f ∩ (K × H), h ∩ (H × K) ∈ cofP, and they are regular in cofP.
Proof. If g is regular in cofP then g −1 ∈ cofP; hence, g −1 f g−1 = g−1 for some f ∈ fP. Hence
by multiplying on the left and the right by g we obtain: f ∩ (K × H) = g, where K = Im(g) and
H = Dom(g).
For the converse, f ∩ (K × H) = (f ∩ (K × H)) ◦ (h ∩ (H × K)) ◦ (f ∩ (K × H)) =
(f ∩ (K × H)) ◦ h ◦ (f ∩ (K × H)); the latter holds by Lemma 4.17. Hence, f ∩ (K × H) has an
inverse in fP, so f ∩ (K × H) belongs to cofP. Similarly, h ∩ (H × K) belongs to cofP. Since they are
mutual inverses, they are regular in cofP. ✷

5.2

Group inverses of elements of fP

After noticing that every regular element of fP has an injective inverse, belonging to an inverse submonoid of fP, we wonder whether we can go even further: Does every regular element in fP have an
inverse in a subgroup of fP? This is of course not the case; for immediate counter-examples consider the
functions that are total but not surjective, or surjective but not total. Even within the subsemigroup
of non-total non-surjective functions of fP there are counter-examples (due to the polynomial balance
and time requirements). Nevertheless, we will find that every regular element of fP is equivalent, with
respect to inversive reduction, to a regular element of fP that has an inverse in a subgroup of fP.
We will also investigate elements of fP that are possibly non-regular, but that have an inverse in
a subgroup of invfP(NP) . Again, we will find that every element of fP is equivalent, with respect to
20

inversive reduction, to an element of fP that has an inverse in a subgroup of invfP(NP) . In particular,
there are elements of fP that are complete with respect to inversive reduction and that have an inverse
in a subgroup of invfP(NP) .
Some definitions about inversive reductions (from [3]) between functions f1 , f2 :
• f1 is simulated by f2 (denoted by f1 4 f2 ) iff there exist β, α ∈ fP such that f1 = β ◦ f2 ◦ α.
• f1 reduces inversively to f2 (notation, f1 6inv f2 ) iff
(1) f1 4 f2 and
(2) for every inverse f2′ of f2 there exists an inverse f1′ of f1 such that f1′ 4 f2′ .
• f, g ∈ fP are equivalent via inversive reduction iff f 6inv g and g 6inv f .
Theorem 5.8 Every function f ∈ fP is equivalent, via inversive reduction, to a function f0 ∈ fP
such that f0 has an inverse in a subgroup of invfP(NP) .
In particular, f0 has an inverse in the group of permutations of 0 Dom(f ) ∪ 1 Im(f ), in invfP(NP) .
Moreover, f0 has an inverse in the group of units of invfP(NP) .
If f (and hence f0 ) is regular, then f0 has an inverse in the group of permutations of 0 Dom(f ) ∪
1 Im(f ), in invfP. Moreover, f0 has an inverse in the group of units of invfP.
Remarks. Since f and f0 are equivalent via reduction it follows immediately that f0 ∈ fP iff f ∈ fP;
and f is regular iff f0 is regular. And by Theorem 4.18, if f is regular then f0 has an inverse in the
inverse monoid invfP.
Proof of Theorem 5.8. (1) With f we associate f0 defined by
Dom(f0 ) = 0 Dom(f ), and
f0 (0 x) = 1 f (x), for all x ∈ Dom(f ).
Similarly, we define f1 by f1 (1 x) = 0 f (x).
To show that f and f0 simulate each other (and similarly for f1 ), we introduce the functions πa
and πa′ for each a ∈ A; they are defined for all z ∈ A∗ by
πa (z) = az, and

πa′ (az) = z, with Dom(πa′ ) = aA∗ .

Then we have:
f0 = π1 ◦ f ◦ π0′ , and f = π1′ ◦ f0 ◦ π0 .
Hence, f and f0 simulate each other.
Let us show that we have an inversive reduction of f0 to f . If f has an inverse f ′ , let us define f1′
by f1′ (1 y) = 0 f ′ (y) for all y ∈ Dom(f ′ ). Then f1′ is an inverse of f0 . And f1′ = π0 ◦ f ′ ◦ π1′ , so f1′ is
simulated by f ′ .
Conversely, let us show that there is an inversive reduction of f to f0 . Let g be any inverse
of f0 , i.e., f0 gf0 (x) = f0 (0 x), all x ∈ Dom(f ). Then h = g ∩ 1A∗ × 0A∗ can be simulated by
g (indeed, h(.) = id0A∗ ◦ g ◦ id1A∗ (.)), and h also satisfies f0 hf0 = f0 . Moreover, h ⊂ 1A∗ × 0A∗
implies that h = k1 for some function k. Then we have f kf = f ; indeed, for all x ∈ Dom(f )
we have f kf (x) = π1′ f0 k1 f0 (0x) = π1′ f0 (0x) = f (x). We saw that k is simulated by k1 (indeed,
k = π0′ ◦ k1 ◦ π1 ). Thus there exists an inverse (namely k) of f that is simulated by g.
This completes the proof that f is equivalent to f0 via inversive reduction. It follows immediately
that f0 ∈ fP iff f ∈ fP, and that f is regular iff f0 is regular.
(2) Let f ′ be any mutual inverse of f with f ′ ∈ cofP, or with f ′ ∈ invfP if f is regular. Let us
now extend f1′ to a group element. Recall that by definition, f1′ (1 y) = 0 f ′ (y) for all y ∈ Dom(f ′ ),
Dom(f1′ ) = 1 Dom(f ′ ) = 1 Im(f ), and Im(f1′ ) = 0 Im(f ). So, Dom(f1′ ) ∩ Im(f1′ ) = ∅, and f1′ only has
orbits of length 1. We extend f1′ to a permutation F ′ of Dom(f1′ ) ∪ Im(f1′ ), defined by
F ′ |Dom(f1′ ) = f1′

and

F ′ |Im(f1′ ) = f1′−1 .

Hence, F ′ = f1′ ∪ f1′−1 . It follows that F ′ ∈ invfP(NP) , since both f1′ and f1′−1 belong to invfP(NP) .
21

Also, F ′ is injective and F ′ ◦ F ′ = idZ , where Z = Dom(f1′ ) ∪ Dom(f1′−1 ); so F ′ = F ′−1 belongs to
a two-element group. Clearly, Dom(F ′ ) = Im(F ′ ) = Z.
Moreover, F ′ is an inverse of f0 . Indeed, for every x ∈ Dom(f ) we have f0 F ′ f0 (0x) = f0 F ′ (1f (x)) =
f0 f1′ (1f (x)), since F ′ = f1′ ∪ f1′−1 and f1′−1 is undefined on 1A∗ ; hence, f0 F ′ f0 (0x) = f0 (0x).
Finally, let us show that if f ′ ∈ invfP then F ′ ∈ invfP. Indeed, when f ′ ∈ invfP then f ′−1 ∈ invfP,
from which it follows (by disjointness of the domains and disjointness of the images) that f1′ ∪ f1′−1 ∈
invfP.
(3) We can extend F ′ to a permutation of all of A∗ (belonging to the group of units of invfP(NP) ): We
simply define F ′ as a permutation of Dom(f1′ ) ∪ Im(f1′ ), as above, and then extend F ′ to the identity
function on A∗ − (Dom(f1′ ) ∪ Im(f1′ )). Since f1′ , idDom(f1′ ) , and idIm(f1′ ) belong to invfP(NP) , it follows
that this extension of F ′ to all of A∗ belongs to invfP(NP) .
Finally, if f is regular then this extension of F ′ belongs to invfP; indeed, in that case, Dom(f1′ ) and
Im(f1′ ) belong to P. ✷
Corollary 5.9 There exists a function that is complete in fP for inversive reduction, and that has
an inverse in the group of units of invfP(NP) .
Proof. In [3] we saw examples of functions F ∈ fP that are complete with respect to inversive
reduction. Then F0 , defined by F0 (0x) = 1 F (x), is also complete (since F and F0 are equivalent via
inversive reduction); and F0 has an inverse in the group of units of invfP(NP) (as we saw in the proof
of Theorem 5.8). ✷
Remark. The group-inverses constructed above belong to invfP(NP) , but not necessarily to cofP. If
there were a complete function in fP that has an inverse in the group of units of cofP then P = NP
(since the group of units of cofP is the same as the group of units of invfP).

6

Appendix: Simple facts about inverses (related to Section 2)

We present some additional properties of invfP that are not used in the rest of the paper.
For f ∈ fP we define the right fixator of f by RFix(f ) = {α ∈ fP : f ◦ α = f }; in other words,
α ∈ RFix(f ) iff α is a right-identity of f . Similarly, the left fixator of f is LFix(f ) = {α ∈ fP : α◦f = f }.
We observe that RFix(f ) ∩ invfP is an inverse monoid; i.e., α ∈ RFix(f ) ∩ invfP implies α−1 ∈
RFix(f ) ∩ invfP. Indeed, if α ∈ invfP satisfies f α = f then f αα−1 = f α−1 ; moreover, f α = f implies
that Dom(f ) ⊆ Im(α), hence αα−1 = idIm(α) acts as a right-identity on f ; hence f = f αα−1 . Thus,
f = f α−1 .
For every α ∈ RFix(f ) we have: α(Dom(f )) ⊆ Dom(f ), α|Dom(f ) ∈ RFix(f ), and α(A∗ −Dom(f )) ⊆
∗
A − Dom(f ).
Every representative choice function of f belongs to RFix(f ), since any right fixator α ∈ RFix(f )
maps every modf -class into itself. But the converse is not true, since a right fixator α does not
necessarily map a modf -class to a single element of the modf -class (as a representative choice function
does).
Proposition 6.1 Let f1′ , f2′ ∈ invfP be inverses of the same element f ∈ fP, such that Dom(fi′ ) =
Im(f ) (i = 1, 2). Then:
(1)

f1′−1 ≡R f2′−1 ≡R idIm(f ) (for the R-relation of invfP), and
idIm(f ) ≡R f (for the R-relation of fP); and
f1′ ≡L f2′ (for the L-relation of invfP).
If f1′ ≡L f2′ and f1′ ≡R f2′ (for the L- and R-relations of fP), then f1′ = f2′ .

(2)

fi′ f ∈ RFix(f ),
f2′ f1′−1 is a bijection from the choice set Im(f1′ ) onto the choice set Im(f2′ );
22

fi′ fi′−1 = idIm(fi′ ) .
fi′−1 fi′ = idIm(f ) .
(3) f2′ f f1′ = f2′ .
(4) If α ∈ RFix(f ), and if f ′ ∈ fP is an inverse of f ∈ fP such that Dom(f ′ ) = Im(f ), then α ◦ f ′ is
also an inverse of f such that Dom(αf ′ ) = Im(f ). So, the monoid RFix(f ) acts on the left on the set
{g′ ∈ invfP : g ′ is an inverse of f and Dom(g′ ) = Im(f )}.
Moreover, this action is transitive, and the action of {α|Dom(f ) : α ∈ RFix(f )} is faithful.
Proof. (1) We saw that fi′−1 = f |Im(fi′ ) , hence fi′−1 = f ◦ idIm(fi′ ) , where Im(fi′ ) ∈ P (since fi′ is
regular); hence idIm(fi′ ) ∈ fP and fi′−1 ≤R f .
Also, fi′ = fi′ f fi′ ≡L f fi′ = idIm(f ) . We also have fi′−1 ≡R idIm(f ) ; indeed, fi′−1 maps Im(fi′ )
bijectively onto Im(f ), so fi′−1 = idIm(f ) ◦ fi′−1 ≤R idIm(f ) ; and idIm(f ) = fi′−1 fi′ ≤R fi′−1 . Moreover,
f ≡R idIm(f ) , hence fi′−1 ≡R f .
The ≡L -equivalence then follows, since in any inverse monoid, x′ ≡R y ′ implies x ≡L y (where z ′
is the inverse of z for any element z).
The fact that f1′ ≡L f2′ and f1′ ≡R f2′ imply f1′ = f2′ is well-known in semigroup theory (see e.g. p.
26 in [5]).
(2) Obviously, f fi′ f = f . The rest is straightforward.
(3) We know that f1′ and f2′ have the same domain, namely Im(f ). And f f1′ |Im(f ) = idIm(f ) , hence
′
f2 f f1′ = f2′ idIm(f ) = f2′ (the latter again holds since Dom(fi′ ) = Im(f )).
(4) If f α = f then f αf ′ f = f f ′ f = f , so αf ′ is also an inverse of f . And Dom(αf ′ ) ⊆ Dom(f ′ ) =
Im(f ); since αf ′ is an inverse of f we also have Im(f ) ⊆ Dom(αf ′ ); hence Dom(αf ′ ) = Im(f ). It
follows that αf ′ ∈ invfP, so RFix(f ) acts on the given set on the left.
Transitivity follows from (f2′ f ) f1′ = f2′ (proved in (3)), where f2′ f ∈ RFix(f ) by (2).
Proof of faithfulness: Note that Dom(f ) ⊆ Dom(α) for all α ∈ RFix(f ). If α1 |Dom(f ) 6= α2 |Dom(f )
then there exists x0 ∈ Dom(f ) such that α1 (x0 ) 6= α2 (x0 ). There exists an inverse f0′ ∈ invfP of
f with Dom(f0′ ) = Im(f ) such that f0′ (f (x0 )) = x0 ; indeed, we can start with any inverse f0′ with
Dom(f0′ ) = Im(f ), and if f0′ (f (x0 )) 6= x0 we can redefine f0′ on f (x0 ); this does not change Dom(f0′ ) (it
just changes the choice set of f0′ ). Now, α1 f0′ f (x0 ) = α1 (x0 ) 6= α2 (x0 ) = α2 f0′ f (x0 ), so α1 f0′ 6= α2 f0′ .
✷
Proposition 6.2 If f ∈ fP is regular, and if Dom(f ◦ α) = Dom(f ), then we have:
α ∈ RFix(f ) iff for every mutual inverse f ′ of f : α ◦ f ′ is also a mutual inverse of f .
(If f is not regular, the Proposition holds for inverses in invfP(NP) .)
Proof. [⇒] If α ∈ RFix(f ) and f ′ is a mutual inverse of f then f αf ′ f = f f ′ f = f ; the first equality
holds because α ∈ RFix(f ). And αf ′ f αf ′ = αf ′ f f ′ = αf ′ (again, using f α = f ). So αf ′ is a mutual
inverse of f .
[⇐] If α 6∈ RFix(f ) then f α(x0 ) 6= f (x0 ) for some x0 ∈ A∗ . If x0 ∈ Dom(f ), let f ′ ∈ fP be a mutual
inverse of f such that f ′ f (x0 ) = x0 ; such a mutual inverse exists (if f ′ f (x0 ) 6= x0 we can redefine f ′
on the one element f (x0 )). Then f αf ′ f (x0 ) = f α(x0 ) 6= f (x0 ), so f αf ′ f 6= f . So there exists a
mutual inverse f ′ such that αf ′ is not an inverse of f . ✷
From the above we conclude that finding an inverse f ′ for f with Dom(f ′ ) = Im(f ) can be broken
up into two steps: (1) find a maximal injective subfunction f ′−1 of f (being a maximal injective
subfunction is equivalent to Im(f ′−1 ) = Im(f )); (2) find the inverse f ′ of f ′−1 . (If f is injective, step
(1) is skipped.)
Proposition 6.3 When f ∈ fP is regular and if Im(β ◦ f ) = Im(f ) we have:
β ∈ LFix(f ) iff for every mutual inverse f ′ of f : f ′ β is also a mutual inverse of f .
(If f is not regular, the Proposition holds for inverses in invfP(NP) .)
23

Proof. [⇒] If β ∈ LFix(f ) and f ′ is a mutual inverse of f then f f ′ β f = f f ′ f = f ; and f ′ β f f ′ β =
f ′ f f ′ β = f ′ β (using βf = f ).
[⇐] If β 6∈ LFix(f ) then βf (x0 ) 6= f (x0 ) for some x0 ∈ A∗ . If βf (x0 ) ∈ Im(f ) then f f ′ β f (x0 ) = β f (x0 )
since f f ′ |Im(f ) = idIm(f ) ; and β f (x0 ) 6= f (x0 ), hence f f ′ β f 6= f . ✷

References
[1] Ch.H. Bennett, “Logical reversibility of computation”, IBM Journal of Research and Development 17.6
(1973) 525-532.
[2] Ch.H. Bennett, “Time/space trade-offs for reversible computation”, SIAM J. on Computing 18(4) (1989)
766-776.
[3] J.C. Birget, “Semigroups and one-way functions”, International J. of Algebra and Computation 25.1-2
(2015) 3-36. – Preprint: http://arXiv.org/abs/1306.1447
[4] J.C. Birget, “Infinitely generated semigroups and polynomial complexity”, International J. of Algebra and
Computation 26.04 (2016) 727-750.
[5] A.H. Clifford, G.B. Preston, The Algebraic Theory of Semigroups, Vol. 1 (Mathematical Survey, No 7 (I))
American Mathematical Society, Providence (1961).
[6] P.A. Grillet, Semigroups, an introduction to the structure theory, Marcel Dekker (1995).
[7] J. Hartmanis, Feasible Computations and Provable Complexity Properties, SIAM/CBMS-NSF Book 30
(1978).
[8] L.H. Hemaspaandra, M. Ogihara, The Complexity Theory Companion, Springer (2002).
[9] M.V. Lawson, Inverse Semigroups: The Theory of Partial Symmetries, World Scientific Publishing (1998).
[10] L.A. Levin, “Universal sequential search problems”, Problemy Peredatshi Informatsii, 9.3 (1973) 115-116.
[11] L.A. Levin, “Randomness conservation inequalities; information and independence in mathematical theories”, Information and Control, 61.1 (1984) 15-37.
[12] M. Li, P. Vitányi, An Introduction to Kolmogorov Complexity and its Applications, Springer (1993, 1997,
2008).
[13] Ch. Papadimitriou, Computational Complexity, Addison-Wesley (1994).

24

