Polynomial-time versus recursive models
From MaRDI portal
Publication:1182471
DOI10.1016/0168-0072(91)90008-AzbMath0756.03021MaRDI QIDQ1182471
Douglas Cenzer, Jeffery B. Remmel
Publication date: 28 June 1992
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(91)90008-a
03C57: Computable structure theory, computable model theory
03D45: Theory of numerations, effectively presented structures
Related Items
Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision, Unnamed Item, Definable Subsets of Polynomial-Time Algebraic Structures, A structure of punctual dimension two, AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES, FOUNDATIONS OF ONLINE STRUCTURE THEORY, Complexity, decidability and completeness, Primitive recursive ordered fields and some applications, Computable embeddability for algebraic structures, Primitive recursive reverse mathematics, Feasibly categorical models, Automatic presentations of structures, A criterion for P-computability of structures, Inversion operations in algebraic structures, Punctually presented structures I: Closure theorems, The complexity of inversion in groups, Existence and uniqueness of structures computable in polynomial time, Algebraic structures computable without delay, Space complexity of abelian groups, Polynomial-time Abelian groups, Recursively presented games and strategies, Countable thin \(\Pi^0_1\) classes, Computable isomorphisms, degree spectra of relations, and Scott families, Feasible graphs with standard universe, Complexity and categoricity, Structures computable in polynomial time. II, The diversity of categoricity without delay, Categoricity for primitive recursive and polynomial Boolean algebras, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, Polynomial computability of fields of algebraic numbers, Eliminating unbounded search in computable algebra, Punctual dimension of algebraic structures in certain classes, Finitely generated structures computable in polynomial time, Complexity issues for the iterated \(h\)-preorders, Quotient structures and groups computable in polynomial time, Searching for applicable versions of computable structures, On efficiency of notations for natural numbers, Punctual copies of algebraic structures, Graphs are not universal for online computability, Online presentations of finitely generated structures, Polynomially computable structures with finitely many generators, The back-and-forth method and computability without delay, Structures computable in polynomial time. I, Well-Quasi Orders and Hierarchy Theory
Cites Work
