×

Polynomial-time versus recursive models. (English) Zbl 0756.03021

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)

MSC:

03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
PDFBibTeX XMLCite
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.