scientific article; zbMATH DE number 1540059

MaRDI QIDQ4519749zbMATH OpenFDO

Authors Argimiro Arratia

Publication date 4 December 2000

zbMATH Keywords

complexity classescomputational complexityfinite model theoryP and NP and PSPACEsatisfiability problem

Mathematics Subject Classification ID

Abstract and axiomatic computability and recursion theory (03D75) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1254648
• Descriptive characterizations of computational complexity
• scientific article; zbMATH DE number 17544
• Finite model theory and its applications.
• scientific article; zbMATH DE number 803291

Cited in

(5)

• Arithmetical definability and computational complexity
• Existential second-order logic over graphs: a complete complexity-theoretic classification
• scientific article; zbMATH DE number 17544 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Computer Science Logic

This page was built for publication:

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