Complexity and categoricity

DOI10.1006/INCO.1997.2676zbMath0892.68045OpenAlexW2079231379MaRDI QIDQ1383162

Douglas Cenzer, Jeffery B. 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)

Related Items (6)

Existence and uniqueness of structures computable in polynomial time ⋮ Structures computable in polynomial time. II ⋮ Structures computable in polynomial time. I ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ Categoricity for primitive recursive and polynomial Boolean algebras ⋮ Space complexity of abelian groups

Cites Work

• Complexity-theoretic algebra. II: Boolean algebras
• Autostability of models
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• Recursively presented games and strategies
• Autostability and computable families of constructivizations
• Feasible graphs with standard universe
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Recursively Categorical Linear Orderings
• Feasible Graphs and Colorings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity and categoricity