Polynomial-time versus recursive models (Q1182471): Difference between revisions

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 \textit{S. Grigorieff} [J. Symb. Logic 55, 260-276 (1990; Zbl 0708.03015)] and \textit{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.