Is there a logic for polynomial time?

DOI10.1093/jigpal/7.3.359zbMath0936.03033OpenAlexW2148283143MaRDI QIDQ4255975

Heinz-Dieter Ebbinghaus

Publication date: 28 June 1999

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

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

zbMATH Keywords

finite modelsdescriptive complexity theoryPTIMEpolynomial time canonization

Mathematics Subject Classification ID

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

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