Inversion operations in algebraic structures

Abstract

We consider a wide series of classes of algorithmic complexity. We fix such a class and investigate the complexity of the inversion operation in classical algebraic structures, like groups or fields. In addition, we analyze the properties of quotient structures.

Keywords

Computability polynomial computability complexity of computations algebraic classes inversion operation

1. Introduction

In the theory of algorithms, there are different approaches to the question which algorithms should be viewed as efficient. The general computability theory studies all algorithms, the theory of primitive recursive functions (p.r.f.) considers only algorithms that do not use the minimization operator, i.e., the operator of unbounded search. Inside the class of p.r.f., there is Grzegorczyk hierarchy consisting of an infinite chain of increasingly complex classes. The theory of effective computations often uses P as the basis class, which consists of all functions computable in polynomial time. Such functions can be treated as computable fairly quickly. Inside P, there exists the subclass L consisting of all functions computable in linear time. In general, there are a lot of different complexity classes in the theory of algorithms, which are primarily related with the computation time of a function.

Let Γ be a complexity class. As a basic object, we consider functions $f : A \to Σ^{*}$ , where Σ is a finite alphabet, $Σ^{*}$ is the set of all words in it, and $A \subseteq Σ^{*}$ , i.e., partial functions on $Σ^{*}$ . We can assume that Γ is some class of functions of this kind, where the alphabet Σ can be arbitrary. Having Γ chosen, we can extend it to many other natural objects. If $f : A \to Σ^{*}$ , where $A \subseteq {(Σ^{*})}^{n}$ , $n ⩾ 1$ , then we say that f is in Γ if the function $f^{'}$ is, $f^{'} (x_{1} * x_{2} * \dots * x_{n}) = f (x_{1}, x_{2}, \dots, x_{n})$ , where ∗ is a new character not in Σ.

We say that a set $A \subseteq {(Σ^{*})}^{n}$ is in Γ if its characteristic function $χ_{A} : {(Σ^{*})}^{n} \to {0, 1}$ is, where 0, 1 are treated as new characters.

Let $A = (A, L^{A})$ be a structure of a finite signature L. We say that $A$ is in Γ if there exists a finite alphabet Σ such that the universe $A \subseteq Σ^{*}$ , and A itself and all functions and predicates from $L^{A}$ are in Γ. A similar definition can be found, for example, in [6]. In short, we say that $A$ is a Γ-computable structure.

Suppose that $Γ = P$ and $A = (A, \cdot)$ is a P-computable group. What can we say about the complexity of the operation $x \mapsto x^{- 1}$ in $A$ ? Clearly, it is computable, since can be constructed by searching $y \in A$ such that $x \cdot y = 1$ . It turns out that we can’t say anything more in many cases. In [3], it is proved that if the center of group $Z (A)$ has an element a of infinite order, then, under some additional assumptions about the complexity of the function $n \mapsto a^{n}$ , there exists a P-computable group $B ≅ A$ , in which the operation $x^{- 1}$ is not even primitively recursive. In particular, this theorem can be applied to the group of integers $(Z, +)$ .

On the other hand, it is proved in [2] that for every P-computable group $A = (A, \cdot)$ , there is a P-computable group $B ≅ A$ in which the operation $x^{- 1}$ is also P-computable. In other words, it can always be improved up to a quickly computable function.

The aim of this article is to try to transfer some facts of this kind to the case of a very general definition of an algorithmic class Γ. For this, we impose some weak constraints on Γ, under which a series of general facts about Γ-computable structures hold. Functions computable in linear time on multi-tape Turing machines are considered here as simplest ones, which should lie in every class Γ.

Further we consider Γ-computable Abelian groups, rings, and fields. At the end, some questions about quotient structures are considered. We say that $A$ is a Γ-computable quotient structure if $A = A_{0} / E$ , where $A_{0}$ is a Γ-computable structure and E is a congruence on $A_{0}$ from Γ.

In [2], the case of $Γ = P$ is considered, and it is proved that every P-computable quotient structure $A$ is isomorphic to a P-computable structure $B$ . Moreover, there always exists a P-computable isomorphism $f : B \to A$ . In [4], it is proved that if $P = NP$ then we can also construct an isomorphism $f : B \to A$ such that f and $f^{- 1}$ are P-computable functions.

In this paper, we also partially generalize these facts to an arbitrary complexity class Γ. At the end, some applications to P-computable and primitive recursive fields are considered.

Note that some generalizations of this form were earlier considered in [5] for classes of Grzegorczyk hierarchy.

We briefly describe the structure of the article. In Section 2, arbitrary complexity classes Γ are discussed. In Section 3, some facts about inversion operations in Abelian groups, rings and fields are proved. In Section 4, we consider quotient structures.

2. Abstract algorithmic classes

Since further we work in different alphabets, note that every set can be called an alphabet. A word in an alphabet Σ is a function $x : n \to Σ$ , where $n = {0, 1, \dots, n - 1}$ is a natural number. In a more traditional notation, x is the sequence of characters $x (0) x (1) \dots x (n - 1)$ , and $n = | x |$ is the length of x. If $x, y \in Σ^{*}$ then $x y$ is the join of them. The notation $x ≼ y$ means that x is an initial subword of y. As a rule, we will work with finite alphabets. Every function x, for which $dom (x)$ is a natural number, is a word in some finite alphabet.

The notation $f : A \to_{p} B$ means that f is a partial function from A to B, that is, $f : A_{0} \to B$ , where $A_{0} \subseteq A$ . If $x \in A_{0}$ then we write $f (x) ↓$ , and $f (x) ↑$ otherwise.

As a basic computing device, we use n-tape Turing machines described in [1]. To compute a function $f (x_{1}, \dots, x_{k})$ on such a machine, we place words $x_{1}, \dots, x_{k}$ on the first k tapes, and get the result $f (x_{1}, \dots, x_{k})$ on the $(k + 1)$ th tape. Here $n ⩾ k + 1$ .

We say that $f : A \to Σ^{*}$ , where $A \subseteq Σ^{*}$ , is computable in linear time if $f (x)$ is computable for $x \in A$ in time $O (| x | + 1)$ on a Turing machine, that is, in time $c (| x | + 1)$ , where c is a constant. A function f is computable in polynomial time, or P-computable, if $f (x)$ is computable in time $O (| x |^{p} + 1)$ , where $p \in ω$ is a constant. For $p = 2, 3, \dots$ , we say about functions computable in quadratic, cubic, etc., time. The time of the form $O (2^{| x |^{p}})$ is called exponential.

Now we formulate the basic definition. Let Γ be a class of function of the form $f : Σ^{*} \to_{p} Σ^{*}$ , where Σ is an arbitrary finite alphabet.

Definition 1.
We say that Γ is an algorithmic class if for every finite alphabet Σ, the following are true:
Γ contains every function $f : Σ^{} \to_{p} Σ^{}$ computable in linear time;

Γ is closed under restriction: if $f \in Γ$ and $A \subseteq dom (f)$ , then $f |_{A} \in Γ$ ;

Γ is closed under joining: if $f, g : Σ^{} \to_{p} Σ^{}$ are in Γ, $h : dom (f) \cap dom (g) \to_{p} Σ^{}$ , and $h (x) = f (x) g (x)$ , then $h \in Γ$ ;

Γ is closed under composition with functions computable in linear time: if $f, g : Σ^{} \to_{p} Σ^{}$ , $f \in Γ$ , and g is computable in linear time, then $g \circ f$ and $f \circ g$ are in Γ.

Natural examples are classes of functions computable in linear, quadratic, polynomial, or exponential time, primitive recursive and computable functions, as well as analogues of these classes using an oracle. In general, there are a lot of such classes.

We aim to make this definition as general as possible, and the conditions as weak as possible. In particular, Γ may be not closed under composition. For example, this holds for the class of functions computable in quadratic time.

We note that including functions in Γ does not depend on the choice of a particular alphabet. Let Σ, $Σ_{1}$ be two finite alphabets of the same cardinality, and let $g : Σ \to Σ_{1}$ be a bijection. The function $h : Σ^{} \to Σ_{1}^{}$ that maps a word $x = a_{1} a_{2} \dots a_{k}$ to $h (x) = g (a_{1}) g (a_{2}) \dots g (a_{k})$ , where $a_{i} \in Σ$ for $i ⩽ k$ , is computable in linear time, and the same holds for $h^{- 1}$ . Let $f : Σ^{} \to_{p} Σ^{}$ be a function in Γ. Considering h, f and $h^{- 1}$ as partial functions on ${(Σ \cup Σ_{1})}^{}$ , we see that $h \circ f \circ h^{- 1}$ is in Γ.

Now we consider the more general case of n-place functions. Suppose that $f : {(Σ^{})}^{n} \to_{p} Σ^{}$ , where $n ⩾ 1$ , ∗ is a new character not in Σ, and $Σ_{1} = Σ \cup {}$ . We say that f is in Γ if the function $f^{'} : Σ_{1}^{} \to_{p} Σ_{1}^{}$ is, where $f^{'} : x_{1} x_{2} * \dots * x_{n} \mapsto f (x_{1}, \dots, x_{n})$ for $⟨ x_{1}, \dots, x_{n} ⟩ \in dom (f)$ . This definition does not depend on the choice of ∗. We show that an analogue of condition 4) holds for n-place functions.
Lemma 1.
Let functions $f : {(Σ^{})}^{n} \to_{p} Σ^{}$ and $g_{1}, \dots, g_{n} : {(Σ^{})}^{k} \to_{p} Σ^{}$ be given. If $f \in Γ$ and all $g_{i}$ , $i ⩽ n$ , are computable in linear time or, vice versa, f is computable in linear time and $g_{i} \in Γ$ for $i ⩽ n$ , then their composition $h (\bar{x}) = f (g_{1} (\bar{x}), \dots, g_{n} (\bar{x}))$ also lies in Γ. Here $dom (h) = {\bar{x} \in {(Σ^{})}^{k} ∣ g_{i} (\bar{x}) ↓ for all i ⩽ n and f (g_{1} (\bar{x}), \dots, g_{n} (\bar{x})) ↓}$ .
Proof.
We consider the second case. All functions $g_{i}^{'} : x_{1} \dots * x_{k} \mapsto g_{i} (x_{1}, \dots, x_{k})$ are in Γ. Since the function $x \mapsto $ on ${(Σ \cup {})}^{}$ is computable in linear time, the function $g : x_{1} \dots * x_{k} \mapsto g_{1} (x_{1}, \dots, x_{k}) * \dots * g_{n} (x_{1}, \dots, x_{k})$ is in Γ. The transition from the last word to $h (x_{1}, \dots, x_{k})$ is performed in linear time. The first case is similar. □

If, in addition, Γ is closed under composition, then the same proof shows that the condition $f, g_{1}, \dots, g_{n} \in Γ$ implies $h \in Γ$ .

We say that a set $A \subseteq {(Σ^{})}^{n}$ is in Γ if $χ_{A} : {(Σ^{})}^{n} \to {0, 1}$ is. It is easy to show that this definition does not depend on the choice of Σ: if $A \subseteq {(Σ^{})}^{n}$ and $Σ \subseteq Σ_{1}$ , $χ_{A} : {(Σ^{})}^{n} \to {0, 1}$ and ${\bar{χ}}_{A} : {(Σ_{1}^{})}^{n} \to {0, 1}$ , then $χ_{A} \in Γ \Leftrightarrow {\bar{χ}}_{A} \in Γ$ .

We repeat the definition from the introduction. Let Γ be an algorithmic class and $A = (A, L^{A})$ be a structure of a finite signature L with universe A. We say that $A$ is a structure in* Γ if there exists a finite alphabet Σ such that $A \subseteq Σ^{}$ and A itself and all operations and relations from $L^{A}$ are in Γ. $A$ is called a quotient structure in* Γ if there exist a structure $A_{0}$ in Γ and a congruence relation E on $A_{0}$ in Γ such that $A = A_{0} / E$ .

We comment the last definition. The set $A_{0} \subseteq Σ^{}$ and the equivalence relation $E \subseteq A_{0}^{2}$ should be in Γ. By definition, the elements of $A$ are equivalence classes of the form $[x] = {y \in A_{0} ∣ x E y}$ , where $x \in A_{0}$ . The set $A = A_{0} / E = {[x] ∣ x \in A_{0}}$ of the described form can be called a quotient set in* Γ. Thus, the universe of a quotient structure in Γ is a quotient set in Γ.

If $A$ , $B$ are two structures in Γ, then we write that $A ≼_{Γ} B$ , $A$ is Γ-reducible to $B$ , if there is an isomorphism $f : A \to B$ from Γ. We say that $A$ and $B$ are Γ-isomorphic, $A ≅_{Γ} B$ , if there exists an isomorphism $f : A \to B$ such that f and $f^{- 1}$ are in Γ.

Now we transfer these natural definitions to the case of quotient structures. Suppose that $A_{0}, B_{0} \subseteq Σ^{}$ , $E \subseteq A_{0}^{2}$ is an equivalence relation on $A_{0}$ , and $F \subseteq B_{0}^{2}$ is an equivalence relation on $B_{0}$ . We say that a mapping on quotient sets $f : A_{0} / E \to B_{0} / F$ is in Γ if there exists a function $f_{0} : A_{0} \to B_{0}$ in Γ such that $f ([x]) = [f_{0} (x)]$ for $x \in A_{0}$ .

Let $A = A_{0} / E$ , $B = B_{0} / F$ be two quotient structures in Γ. The notation $A ≼_{Γ} B$ again means that there is an isomorphism $f : A \to B$ in Γ, and $A ≅_{Γ} B$ means that there is an isomorphism $f : A \to B$ for which f and $f^{- 1}$ are in Γ.

Identifying an element $x \in Σ^{}$ with the set ${x}$ , we can consider structures in Γ as a partial case of quotient structures in Γ with the trivial relation E. The notations $A ≼_{Γ} B$ and $A ≅_{Γ} B$ are coordinated in this case.
3. Constructing inverse operations

Proposition 1.
Suppose that Γ is an algorithmic class, and $A = (A, +)$ is a commutative semigroup in Γ where the following reduction law holds: if $x, y, z \in A$ and $x + z = y + z$ , then $x = y$ . Then there exists an Abelian group $B = (B, +, -)$ and an isomorphic embedding $f : A \to B$ such that $B$ is a quotient structure in Γ and $f \in Γ$ .
Proof.
The proof is based on a well-known algebraic construction, see [8, Ch. I, §9]. Let $A \subseteq Σ^{}$ , where Σ is a finite alphabet. We assume that $A^{2} = {x y ∣ x, y \in A}$ , where $* \notin Σ$ , and denote words $x * y \in A^{2}$ as $⟨ x, y ⟩$ . Define a relation $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \Leftrightarrow x + y^{'} = x^{'} + y$ on $A^{2}$ . The set $A^{2}$ and the relation ≡ are in Γ. We show this for $A^{2}$ . The functions $x * y \mapsto x$ and $x * y \mapsto y$ on $A^{2}$ are computable in linear time, hence, the functions $x * y \mapsto χ_{A} (x)$ and $x * y \mapsto χ_{A} (y)$ are in Γ, and also the function $x * y \mapsto χ_{A} (x) * χ_{A} (y)$ . The function $χ_{A} (x) * χ_{A} (y) \mapsto χ_{A} (x) \cdot χ_{A} (y)$ is computable in linear time.

Clearly, ≡ is reflexive and symmetric. The transitivity check looks as follows. If $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \equiv ⟨ x^{″}, y^{″} ⟩$ then $x + y^{'} = x^{'} + y$ , $x^{'} + y^{″} = x^{″} + y^{'}$ , hence $x + y^{'} + y^{″} = x^{'} + y + y^{″} = x^{″} + y + y^{'}$ and $x + y^{″} = x^{″} + y$ by the reduction law.

We define the following two operations on $A^{2}$ : $⟨ x, y ⟩ + ⟨ x_{1}, y_{1} ⟩ = ⟨ x + x_{1}, y + y_{1} ⟩$ and $- ⟨ x, y ⟩ = ⟨ y, x ⟩$ , which are in Γ. A direct check shows that ≡ is a congruence with respect to them. It is clear that + is commutative and associative. We define $B = (A^{2}, +, -) / \equiv$ . Let $[x, y]$ denote the equivalence class of a pair $⟨ x, y ⟩$ . Let $B = (B, +, -)$ . Since $[x, x] = [y, y]$ and $[x, y] + [z, z] = [x, y]$ , the class $[x, x] = 0$ is the zero in $B$ , and $[x, y] + (- [x, y]) = [x + y, x + y] = 0$ . We have that $B$ is an Abelian group. Choose $a \in A$ and construct $f : A \to B$ as $f (x) = [a + x, a]$ .

If $x, y \in A$ then $f (x) + f (y) = [a + a + x + y, a + a] = [a + x + y, a] = f (x + y)$ . If $f (x) = f (y)$ then $[a + x, a] = [a + y, a]$ , $a + x + a = a + y + a$ , and $x = y$ . We see that f is an isomorphic embedding. It is easy to check that $f \in Γ$ . □
Theorem 1.
Let Γ be an algorithmic class and $A = (A, +)$ be an Abelian group in Γ. Then there exists an Abelian group $B = (B, +, -)$ such that $A ≼_{Γ} (B, +)$ and $B$ is a quotient structure in Γ.
Proof.
If $A$ is an Abelian group then it is also a commutative semigroup with the reduction law, and we can use Proposition 1. It remains to note that f is an isomorphism of $A$ and $(B, +)$ in this case, that is, to check surjectivity.

We consider $x, y \in A$ and choose $z = x - y$ . Then $f (z) = [a + z, a] = [y + z, y] = [x, y]$ . □

We now prove a similar assertion for rings, including non-associative ones, slightly strengthening the requirements for Γ.
Proposition 2.
Suppose that Γ is an algorithmic class closed under composition, and $A = (A, +, \cdot)$ is a structure in Γ in which + is an associative and commutative operation and for every $x, y, z \in A$ , the following hold:
$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ and $(y + z) \cdot x = (y \cdot x) + (z \cdot x)$ ;

if $x + z = y + z$ then $x = y$ .

Then there exists a ring $B = (B, +, \cdot, -)$ and an isomorphic embedding $f : A \to B$ in Γ such that $B$ is a quotient structure in Γ.

If, in addition, the operation · in $A$ is associative, then $B$ is also an associative ring.
Proof.
The proof is a direct generalization of Proposition 1. We suppose that $A \subseteq Σ^{}$ , the elements of $A^{2}$ are treated as words $x y$ , where $x, y \in A$ , and are denoted by $⟨ x, y ⟩$ . Again $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \Leftrightarrow x + y^{'} = x^{'} + y$ . As we have seen, it is an equivalence relation in Γ.

Since a pair $⟨ x, y ⟩$ corresponds to $x - y$ in meaning in $B$ , we define on $A^{2}$ the following operations: $⟨ x, y ⟩ + ⟨ x_{1}, y_{1} ⟩ = ⟨ x + x_{1}, y + y_{1} ⟩$ , $- ⟨ x, y ⟩ = ⟨ y, x ⟩$ , and $⟨ x, y ⟩ \cdot ⟨ x_{1}, y_{1} ⟩ = ⟨ x x_{1} + y y_{1}, x y_{1} + y x_{1} ⟩$ .

We have proved that ≡ is a congruence with respect to + and −. Show this for ·. We suppose that $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩$ , and check that $⟨ x, y ⟩ \cdot ⟨ x_{1}, y_{1} ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \cdot ⟨ x_{1}, y_{1} ⟩$ . By definition $x + y^{'} = x^{'} + y$ . We need to prove that $\begin{matrix} x x_{1} + y y_{1} + x^{'} y_{1} + y^{'} x_{1} = x^{'} x_{1} + y^{'} y_{1} + x y_{1} + y x_{1}, \end{matrix}$ which is equivalent to $\begin{matrix} (x + y^{'}) x_{1} + (y + x^{'}) y_{1} = (x^{'} + y) x_{1} + (y^{'} + x) y_{1} . \end{matrix}$ The equivalence preservation in the second argument is checked similarly. Now we prove, for example, that $\begin{matrix} ⟨ x, y ⟩ \cdot (⟨ x_{1}, y_{1} ⟩ + ⟨ x_{2}, y_{2} ⟩) = ⟨ x, y ⟩ \cdot ⟨ x_{1}, y_{1} ⟩ + ⟨ x, y ⟩ \cdot ⟨ x_{2}, y_{2} ⟩ . \end{matrix}$ The left expression is equal to $\begin{matrix} ⟨ x, y ⟩ \cdot ⟨ x_{1} + x_{2}, y_{1} + y_{2} ⟩ = ⟨ x (x_{1} + x_{2}) + y (y_{1} + y_{2}), y (x_{1} + x_{2}) + x (y_{1} + y_{2}) ⟩ . \end{matrix}$ The right one is equal to $\begin{matrix} ⟨ x x_{1} + y y_{1} + x x_{2} + y y_{2}, y x_{1} + x y_{1} + y x_{2} + x y_{2} ⟩ . \end{matrix}$ We have the same answer. The second distributivity is similar.

Using rather cumbersome calculations, one can show that the associativity of · in $A$ implies the associativity of · in $A^{2}$ . Since Γ is closed under composition, the multiplication in $A^{2}$ is a function in Γ.

Next, we repeat the reasoning from Proposition 1. Let $B = (A^{2}, +, \cdot, -) / \equiv$ . It is a quotient structure in Γ. Let $[x, y]$ be the equivalence class of a pair $⟨ x, y ⟩$ . We have proved that $(B, +, -)$ is a Abelian group, the associativity and distributivity of multiplication are preserved under factorization.

Let $f (x) = [a + x, a]$ . If $x, y \in A$ then $f (x) \cdot f (y) = [a + x, a] \cdot [a + y, a] = [(a + x) (a + y) + a^{2}, (a + x) a + a (a + y)] = [e + x y, e] = [a + x y, a] = f (x y)$ , where $e = 2 a^{2} + x a + a y$ . We see that f is an isomorphic embedding. □
Theorem 2.
Let Γ be an algorithmic class closed under composition, and let $A = (A, +, \cdot)$ be a ring in Γ, not necessarily associative. Then there exists a ring $B = (B, +, \cdot, -)$ such that $A ≼_{Γ} (B, +, \cdot)$ and $B$ is a quotient structure in Γ.
Proof.
As in Theorem 1, we apply Proposition 2 to $A$ and get an embedding $f : A \to B$ , which is an isomorphism in this case. The proof of the latter fact literally repeats Theorem 1. □

Like Proposition 2, this theorem also holds for non-associative rings. If $A$ has a unity 1, then the theorem becomes obvious, since $- x = - 1 \cdot x$ .

Let $A = (A, +, \cdot)$ be a commutative associative ring with zero 0. An element $x \in A$ is called a zero divisor if $x \neq 0$ and there exists $y \neq 0$ such that $x \cdot y = 0$ . To consider fields as structures with total operations, we assume that $0^{- 1} = 0$ . Proposition 3.
Let Γ be an algorithmic class closed under composition, and let $A = (A, +, \cdot)$ be a commutative associative ring without zero divisors in Γ. Then there exist a field $B = (B, +, \cdot, -,^{- 1})$ and an isomorphic embedding $f : A \to B$ such that $B$ is a quotient structure in Γ and $f \in Γ$ .
Proof.
If $A = {0}$ then we can take the two-element field as $B$ . Let $A \neq {0}$ . To prove the proposition, we just need to carefully write down the well-known construction of the field of quotients. Suppose that $A \subseteq Σ^{}$ and 0 is the zero of $A$ . Let $S = {x y ∣ x, y \in A and y \neq 0}$ , where $* \notin Σ$ . The elements of S will be denoted as $⟨ x, y ⟩$ . They correspond in meaning to fractions $\frac{x}{y}$ from $B$ .

We define the relation $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \Leftrightarrow x y^{'} = x^{'} y$ on S. It lies in Γ, and clearly is reflexive and symmetric. If $⟨ x, y ⟩ \equiv ⟨ x^{'}, y^{'} ⟩ \equiv ⟨ x^{″}, y^{″} ⟩$ , then $x y^{'} = x^{'} y$ , $x^{'} y^{″} = x^{″} y^{'}$ , and $x y^{'} y^{″} = x^{'} y^{″} = x^{″} y^{'} y$ . The last equality implies $x y^{″} = x^{″} y$ in a ring without zero divisors, and $⟨ x, y ⟩ \equiv ⟨ x^{″}, y^{″} ⟩$ .

We choose a non-zero element a in A, and define the following four operations on S: $⟨ x, y ⟩ + ⟨ x_{1}, y_{1} ⟩ = ⟨ x y_{1} + x_{1} y, y y_{1} ⟩$ , $⟨ x, y ⟩ \cdot ⟨ x_{1}, y_{1} ⟩ = ⟨ x x_{1}, y y_{1} ⟩$ , $- ⟨ x, y ⟩ = ⟨ - a \cdot x, a y ⟩$ , ${⟨ x, y ⟩}^{- 1} = ⟨ y, x ⟩$ for $x \neq 0$ , and ${⟨ 0, y ⟩}^{- 1} = ⟨ 0, y ⟩$ .

It remains to prove that ≡ is a congruence on S with respect to these operations, and that all axioms of fields hold in the quotient structure $B = (S, +, \cdot, -,^{- 1}) / \equiv$ , see [9, §13]. Let $[x, y]$ denote the equivalence class of a pair $⟨ x, y ⟩$ . Then the element $[0, a]$ is the zero in $B$ , and $[a, a]$ is the unity.

If $x \in A$ then we define $f (x) = [a x, a]$ . It is easy to check that $f (x) + f (y) = f (x + y)$ , $f (x) \cdot f (y) = f (x \cdot y)$ , and $f (x) = [0, a]$ implies $x = 0$ . We get the desired isomorphic embedding from Γ. □
Theorem 3.
Let Γ be an algorithmic class closed under composition, and let $A = (A, +, \cdot)$ be a field in Γ. Then there exists a field $B = (B, +, \cdot, -,^{- 1})$ such that $A ≼_{Γ} (B, +, \cdot)$ and $B$ is a quotient structure in Γ.
Proof.
We apply Proposition 3 to $A$ and show that f is an isomorphism in this case. Let $[x, y] \in B$ . If $z = x y^{- 1}$ then $f (z) = [a x y^{- 1}, a] = [x, y]$ . □

4. Transition from quotient structures to usual structures

We have constructed above a series of Γ-computable quotient structures. Now we consider a transition from a quotient structure to an isomorphic usual structure. First, we define an analogue of the class NP for an arbitrary algorithmic class Γ. Let Σ be a finite alphabet and $R \subseteq {(Σ^{*})}^{2}$ . We say that R is a polynomially bounded relation if there exists a polynomial $P (n) \in N [n]$ with natural coefficients such that $R (x, y) \Rightarrow | y | ⩽ P (| x |)$ . R is called a linearly bounded relation if the polynomial $P (n)$ has degree 1, i.e., there are constants $c, d \in N$ such that $R (x, y) \Rightarrow | y | ⩽ c | x | + d$ .

Let Γ be an algorithmic class and A be a set. We say that $A \in NP (Γ)$ if there exist a finite alphabet Σ and a polynomially bounded relation $R \subseteq {(Σ^{*})}^{2}$ in Γ such that for every x, the equivalence $x \in A \Leftrightarrow \exists y R (x, y)$ holds. In this case $A \subseteq Σ^{*}$ . If the relation R in this definition is linearly bounded, then $A \in NL (Γ)$ . As usual, a k-place set A is in $NP (Γ)$ if $A^{'} = {x_{1} * x_{2} * \dots * x_{k} ∣ ⟨ x_{1}, x_{2}, \dots, x_{k} ⟩ \in A}$ is.

We clarify how an n-tape Turing machine with an oracle $H \subseteq Σ^{*}$ in an alphabet Σ works. We can assume that one tape is reserved for questions to the oracle. We write a word x on it, place a head at the end of x, turn to the oracle, and get the answer 1 on the same tape after x if $x \in H$ , and the answer 0 if $x \in Σ^{*} ∖ H$ . If $x \notin Σ^{*}$ then the machine remains in the original state, i.e., is looping. The query to the oracle takes 1 step of work.

By ${LinTime}^{Γ}$ we denote the class of all functions $f : Σ^{*} \to_{p} Σ^{*}$ computable in linear time with some oracle in Γ.

Theorem 4.

Suppose that Γ is an algorithmic class closed under composition, $NL (Γ) \subseteq Γ$ , and ${LinTime}^{Γ} \subseteq Γ$ . Then for every quotient structure $A$ in Γ, there exists a structure $B$ in Γ such that $A ≅_{Γ} B$ .

Proof.

Let $A = A_{0} / E$ , where $A_{0}$ is a structure in Γ, $A_{0} \subseteq Σ^{*}$ , and $E \subseteq A_{0}^{2}$ is a congruence in Γ. We choose a standard order ⩽ on $Σ^{*}$ , comparing words first by length, and then lexicographically, fixing some order on Σ. Then define a relation $M (x)$ on $Σ^{*}$ by the formula $\begin{matrix} \neg M (x) \Leftrightarrow \exists y (y < x & y E x) . \end{matrix}$ By hypothesis $\neg M (x) \in Γ$ . Hence, $M (x) \in Γ$ . Next, we define a relation $\begin{matrix} P (x, y) \Leftrightarrow \exists z [y z E x & M (y z)] . \end{matrix}$ Again $P \in Γ$ . Let $Σ = {a_{1}, \dots, a_{n}}$ . If $x \in A_{0}$ then let $μ (x)$ denote the unique element of $A_{0}$ such that $μ (x) E x$ and $M (μ (x))$ . We describe an algorithm for computing $μ (x)$ .

Using P as an oracle, we define the values $P (x, a_{1}), P (x, a_{2}), \dots, P (x, a_{n})$ . If $P (x, a_{i_{1}}) = 1$ then $a_{i_{1}} ≼ μ (x)$ . Next, we define the values $P (x, a_{i_{1}} a_{j})$ for all $j ⩽ n$ in the same way, and find $a_{i_{2}}$ such that $a_{i_{1}} a_{i_{2}} ≼ μ (x)$ , etc.

Since $| μ (x) | ⩽ | x |$ , we find $μ (x)$ after no more than $| x |$ cycles, making at most $n | x |$ requests to the oracle. Therefore $μ (x)$ is in the class ${LinTime}^{Γ}$ , and by hypothesis $μ \in Γ$ .

Let $B = {x \in A_{0} ∣ μ (x) = x}$ . It is a set in Γ. We define an interpretation of L on B so that the mapping $g : A \to B$ , $g ([x]) = μ (x)$ , becomes an isomorphism. For this, we need to restrict the predicates to B, and define every operation f by the formula $f^{B} (x_{1}, \dots, x_{k}) = μ (f^{A_{0}} (x_{1}, \dots, x_{k}))$ . We obtain a structure $B$ in Γ, for which $g^{- 1}$ can be defined by the identical function. □

If the signature of $A$ has no functions, then the closure condition under composition for Γ can be removed from the formulation. In this case, the conditions of the theorem hold, for example, for the class Γ of functions $f (x)$ computable in exponential time, as well as in time of the form $O (2^{| x |^{p}})$ , where a constant $p ⩾ 1$ is fixed.

One of the most interesting cases is $Γ = P$ . The condition ${LinTime}^{P} \subseteq P$ is met. If, in addition, $P = NP$ , then $NL (P) \subseteq P$ and every P-computable quotient structure is P-computably isomorphic to a usual P-computable structure. The latter statement cannot be refuted without proving that $P \neq NP$ . This fact was established in [4].

Moreover, it is proved in [2] that this is always true if we weaken requirements for the isomorphism: for every P-computable quotient structure $A$ , there exist a P-computable structure $B$ and a P-computable isomorphism $f : B \to A$ . Combining this fact with Theorem 3, we obtain the following:

Corollary 1.

Let $A = (A, +, \cdot)$ be a P-computable field. Then there exists a P-computable field $A_{1} = (A, +, \cdot, -,^{- 1})$ isomorphic to it.

If, in addition, $P = NP$ , then we can assert that $A ≼_{P} (A_{1}, +, \cdot)$ .

For groups (not only Abelian), a similar fact is proved in [3].

Suppose that Σ, $Σ_{1}$ are two finite alphabets and $| Σ |, | Σ_{1} | ⩾ 2$ . It is well known that there exists a bijection $g : Σ^{*} \to Σ_{1}^{*}$ such that g and $g^{- 1}$ are computable in quadratic time. Really, it is a function translating numbers from one number system to another, up to technical details. If we want to define the notion of a primitive recursive function $f : Σ^{*} \to Σ^{*}$ , then it is natural to assume that g preserves this property. Hence it suffices to consider the case $Σ = {0, 1}$ . Let $bin (x) \in {0, 1}^{*}$ be the standard binary representation of a number $x \in ω$ . The function $h (x) = y$ , where $bin (x + 1) = 1 y$ , is a natural bijection between ω and ${0, 1}^{*}$ . We say that $f : {0, 1}^{*} \to {0, 1}^{*}$ is primitive recursive if the function $h^{- 1} \circ f \circ h$ is. Then every $f_{1} \subseteq f$ also has this property.

If Γ is equal to the class of computable or primitive recursive functions, then the conditions of Theorem 4 are obviously fulfilled, and the theorem itself is simple and well known.

Corollary 2.

Let Γ be the class of p.r.f. and let $A = (A, +, \cdot)$ be a field in Γ. Then there is a field $A_{1} = (A_{1}, +, \cdot, -,^{- 1})$ in Γ such that $A ≅_{Γ} (A_{1}, +, \cdot)$ .

In conclusion, we note that the notion of a function computable in polynomial time does not depend on the choice of a particular Turing machine. Unfortunately, this does not hold for functions computable in linear time from Definition 1. Replacing linear time by polynomial time there, we get a definition that does not depend on the choice of a computing device. Alas, Theorem 1, for example, will become less general in this case, and some interesting cases remain outstanding. Therefore, we prefer to use the current definition, fixing instead multi-tape Turing machines. The functions computed on them in linear time form a simple and simultaneously rather rich class.

Speaking about structures $A$ in Γ, we do not impose any restrictions on their universe A, except that it is a set in Γ. In [7], an example of an infinite computable graph is constructed which does not have a primitive recursive isomorphic presentation with universe ω. Since this graph is a structure without functions, it has a P-computable presentation $A = (A, P)$ , where P is a two-place predicate [6]. However, it cannot have a P-computable presentation with universe B such that there is a primitive recursive injection $f : ω \to B$ . The question about universe can be important in some situation.

Footnotes

Acknowledgements

The author is grateful to V.L. Selivanov for discussions concerning the topics of the paper, as well as S.S. Goncharov, N.A. Bazhenov, and A.V. Nechesov for suggestions for improving the results of the work.

The work is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.

References

A.V.

Aho,

J.E.

Hopcroft and

J.D.

Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

Alaev, Quotient structures and groups computable in polynomial time, Lecture Notes in Computer Science13296 (2022), 35–45. doi:10.1007/978-3-031-09574-0_3.

P.E.

Alaev, The complexity of inversion in groups, Algebra and Logic (2023), accepted for publication.

P.E.

Alaev and

V.L.

Selivanov, Fields of algebraic numbers computable in polynomial time. II, Algebra and Logic60(6) (2021), 349–359. doi:10.1007/s10469-022-09661-3.

P.E.

Alaev and

V.L.

Selivanov, Searching for applicable versions of computable structures, Lecture Notes in Computer Science12813 (2021), 1–11. doi:10.1007/978-3-030-80049-9_1.

Cenzer and

Remmel, Polynomial time versus recursive models, Annals of Pure and Applied Logic54(1) (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.

Kalimullin,

Melnikov and

K.M.

Ng, Algebraic structures computable without delay, Theoretical Computer Science674 (2017), 73–98. doi:10.1016/j.tcs.2017.01.029.

Lang, Algebra, Addison-Wesley Publishing Company, Reading, MA, 1965.

B.L.

van der Waerden, Algebra I, Springer-Verlag, 1971.