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