Is first order contained in an initial segment of PTIME?

DOI10.1007/BFB0022260MaRDI QIDQ4474843zbMATH OpenFDO

Authors Alexei P. Stolboushkin, Michael A. Taitslin

Publication date 21 July 2004

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

Full work available at URL https://doi.org/10.1007/BFB0022260

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4008383
• Logical hierarchies in PTIME
• Infinitary logic and inductive definability over finite structures
• scientific article; zbMATH DE number 4009811
• scientific article; zbMATH DE number 969067

Cited in

(1)

• First order logic, fixed point logic and linear order

This page was built for publication: Is first order contained in an initial segment of PTIME?

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