Polynomially Computable Structures with Finitely Many Generators
- PDF / 175,270 Bytes
- 7 Pages / 594 x 792 pts Page_size
- 104 Downloads / 189 Views
Algebra and Logic, Vol. 59, No. 3, July, 2020 (Russian Original Vol. 59, No. 3, May-June, 2020)
COMMUNICATIONS
POLYNOMIALLY COMPUTABLE STRUCTURES WITH FINITELY MANY GENERATORS P. E. Alaev∗
UDC 510.52+512.5+512.62 Presented by Associate Editor S. S. Goncharov
INTRODUCTION Let L = (P1 , . . . , Pr ; f1 , . . . , fu ; c1 , . . . , cv ) be a finite language consisting of relations, operations, and constants. An L-structure A is said to be finitely generated if there is a finite set of elements e¯ = e1 , . . . , en such that every substructure of A that includes e¯ is equal to A . In this case the elements e¯ are called generators for A . In the present paper, we prove a simple criterion describing finitely generated structures A that have an isomorphic presentation computable in polynomial time (Thms. 2 and 3). As a corollary, we establish the following fact: if an arbitrary structure B is computable in polynomial time, then so is each of its finitely generated substructures A . The obtained criterion is applied to a series of classical algebraic objects, producing a corresponding criterion in every particular class. We recall the definition of a polynomially computable structure. If Σ is a finite alphabet, then Σ∗ denotes the set of all words in this alphabet. Let A be a structure of a finite language L. We say that A is computable in polynomial time (shortly, p-computable) if there exists a finite alphabet Σ such that A ⊆ Σ∗ \ {∅}, and A itself and all relations and operations in L are computable in polynomial time (see [1]). We assume standard definitions when saying that an operation f : An → Σ∗ and a relation P ⊆ An are computable in polynomial time. ∗
The study was carried out within the framework of the state assignment to Sobolev Institute of Mathematics SB RAS (project No. 0314-2019-0002) and supported by RFBR (project No. 20-01-00300).
Sobolev Institute of Mathematics. Novosibirsk State University, Novosibirsk, Russia; [email protected]. Translated from Algebra i Logika, Vol. 59, No. 3, pp. 385-394, May-June, 2020. Russian DOI: 10.33048/alglog.2020.59.307. Original article submitted July 24, 2020; accepted October 21, 2020.
266
c 2020 Springer Science+Business Media, LLC 0002-5232/20/5903-0266
We make some remarks on the authorship of the given theorems. The question of when a finitely generated structure has a p-computable presentation is not new. Censer and Remmel formulated a similar criterion in a chapter written in [2, Thm. 4.7, p. 411]: if r = 0 then a structure A with generators e¯ has a p-computable presentation iff the condition of Theorem 2 holds, together with the following: (i) A ⊆ {0, 1}∗ is a set computable in double exponential time. The text says that this theorem is unpublished, and also that it is due to Remmel and Friedman. To our knowledge, its proof has not yet been published. Thus we can say that in the present paper the additional condition (i) is removed from the theorem, and its proof is given. A certain flaw of the previous statement is that condition (i) in this form is meaningless.
Data Loading...
