Is there a logic for polynomial time?

DOI10.1093/JIGPAL/7.3.359MaRDI QIDQ4255975zbMATH OpenOpenAlexFDO

Authors Heinz-Dieter Ebbinghaus

Publication date 28 June 1999

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/jigpal/7.3.359

zbMATH Keywords

descriptive complexity theoryfinite modelsPTIMEpolynomial time canonization

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15) Inductive definability (03D70)

Recommendations

• Is polynomial time choiceless?
• scientific article; zbMATH DE number 4049049
• Linear logic and polynomial time
• scientific article; zbMATH DE number 1421070
• Polynomial time in untyped elementary linear logic
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• On datalog vs polynomial time
• scientific article; zbMATH DE number 1670472
• scientific article; zbMATH DE number 62443

Cited in

(4)

• scientific article; zbMATH DE number 1223623 (Why is no real title available?)
• Is polynomial time choiceless?
• On polynomial time computation over unordered structures
• A logic for PTIME and a parameterized halting problem

This page was built for publication: Is there a logic for polynomial time?

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