Choiceless polynomial time logic: Inability to express

DOI10.1007/3-540-44622-2_6MaRDI QIDQ2753668zbMATH OpenFDO

Authors S. Shelah

Publication date 3 December 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9807179

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Is polynomial time choiceless?
• Characterising choiceless polynomial time with first-order interpretations
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Choiceless polynomial time computation and the zero-one law
• Choiceless polynomial time

Cited in

(8)

• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Symbioses between mathematical logic and computer science
• Choiceless polynomial time computation and the zero-one law
• Is polynomial time choiceless?
• Choiceless computation and symmetry
• Is there a logic for polynomial time?
• Characterising choiceless polynomial time with first-order interpretations
• Choiceless Logarithmic Space

This page was built for publication: Choiceless polynomial time logic: Inability to express

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