Cenzer, Douglas; Remmel, Jeffrey Polynomial-time versus recursive models. (English) Zbl 0756.03021 Ann. Pure Appl. Logic 54, No. 1, 17-58 (1991). Roughly speaking, a polynomial-time presented structure is one where the universe is \(p\)-time and the relation and function symbols are \(p\)-time computable. Clearly there are a number of variations on this theme, for instance we need to consider if the universe is \(\Sigma^*\), or a \(p\)- time subset of \(\Sigma^*\), and how \(\Sigma^*\) is coded. These objects were essentially first studied by S. Grigorieff [J. Symb. Logic 55, 260-276 (1990; Zbl 0708.03015)] and A. Nerode and the second author [e.g., Ann. Pure Appl. Logic 44, 71-99 (1989; Zbl 0703.03023)], and are related not only to effective mathematics but to, for instance, online algorithms. As the title suggests, the authors compare the various notions of \(p\)-time presentation with the notion of recursive presentation. The main question is whether a given recursive structure is isomorphic to a \(p\)-time one. The answer is yes for relational structures, but counterexamples are given for Abelian groups, and for relational structures with universe \(\Sigma^*\) needed. As with the Grigorieff result, the more difficult positive arguments need not only padding but some model theory combined with a priority argument. Reviewer: R.Downey (Ithaka) Cited in 2 ReviewsCited in 44 Documents MSC: 03D45 Theory of numerations, effectively presented structures 03C57 Computable structure theory, computable model theory Keywords:polynomial-time presented structure; recursive presentation; recursive structure Citations:Zbl 0708.03015; Zbl 0703.03023 PDFBibTeX XMLCite \textit{D. Cenzer} and \textit{J. Remmel}, Ann. Pure Appl. Logic 54, No. 1, 17--58 (1991; Zbl 0756.03021) Full Text: DOI References: [1] Enderton, H., A Mathematical Introduction to Logic (1986), Academic Press: Academic Press New York [2] Goncharov, S. S., Some properties of the constructivization of Boolean algebras, Sib. Mat. Zh., 16, 203-214 (1975) · Zbl 0326.02033 [3] Grigorieff, S., Every recursive linear ordering has a copy in DTIME \((n)\), J. Symbolic Logic, 55, 260-276 (1990) · Zbl 0708.03015 [4] Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relations to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 [5] Nerode, A.; Remmel, J., Complexity theoretic algebra II: the free Boolean algebra, Ann. Pure Appl. Logic, 41, 71-99 (1989) · Zbl 0703.03023 [6] Remmel, J., Recursive Boolean algebras, (Monk, J. D., Handbook of Boolean Algebras (1989), North-Holland: North-Holland Amsterdam), 1099-1165 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.