Complexity and categoricity

DOI10.1006/INCO.1997.2676MaRDI QIDQ1383162zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Jeffrey Remmel

Publication date 4 May 1998

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1997.2676

zbMATH Keywords

feasible modelfeasible Scott family of formulas

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 806746
• Computability-theoretic categoricity and Scott families
• Structures computable in polynomial time. II
• Structures computable in polynomial time. I

Cites work

• Autostability and computable families of constructivizations
• Autostability of models
• Complexity-theoretic algebra. II: Boolean algebras
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Feasible Graphs and Colorings
• Feasible graphs with standard universe
• scientific article; zbMATH DE number 4087025 (Why is no real title available?)
• scientific article; zbMATH DE number 176212 (Why is no real title available?)
• scientific article; zbMATH DE number 176213 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 806746 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Polynomial-time Abelian groups
• Polynomial-time versus recursive models
• Recursively Categorical Linear Orderings
• Recursively presented games and strategies

Cited in

(10)

• Space complexity of abelian groups
• Structures computable in polynomial time. II
• Categoricity for primitive recursive and polynomial Boolean algebras
• Effective categoricity of automatic equivalence and nested equivalence structures
• Structures computable in polynomial time. I
• Classification and complexity of problems.
• Existence and uniqueness of structures computable in polynomial time
• Decomposing the complexity quotient category
• Complexity of hyperconcepts
• Preserving categoricity and complexity of relations

This page was built for publication: Complexity and categoricity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1383162)