Computational complexity on the blackboard

DOI10.3233/FI-2017-1523MaRDI QIDQ4595599zbMATH OpenOpenAlexFDO

Authors Eryk Kopczyński

Publication date 5 December 2017

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2017-1523

zbMATH Keywords

alternationcellular automataSavitch theorem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 4106275
• Complexity theory basics: NP and NL
• scientific article; zbMATH DE number 218387
• scientific article; zbMATH DE number 578252
• Computational Complexity

Cited in

(5)

• scientific article; zbMATH DE number 4106275 (Why is no real title available?)
• Axiomatizing rectangular grids with no extra non-unary relations
• Computational complexity
• Black-Box and Data-Driven Computation
• Computational complexity. A conversation with Bill Gasarch

This page was built for publication: Computational complexity on the blackboard

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