An imperative language characterizing PTIME algorithms

MaRDI QIDQ5213552zbMATH OpenFDO

Authors Yoann Marquer, Pierre Valarcher

Publication date 3 February 2020

Mathematics Subject Classification ID

Theory of programming languages (68N15) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)

Recommendations

• LOGSPACE and PTIME characterized by programming languages
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• On the computational complexity of imperative programming languages
• Some Programming Languages for Logspace and Ptime
• A representation theorem for primitive recursive algorithms

Cited in

(3)

• Implicit characterizations of FPTIME and NC revisited
• LOGSPACE and PTIME characterized by programming languages
• Axiomatization and characterization of BSP algorithms

This page was built for publication: An imperative language characterizing PTIME algorithms

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