A random NP-complete problem for inversion of 2D cellular automata

DOI10.1007/3-540-59042-0_65MaRDI QIDQ4596613zbMATH OpenOpenAlexFDO

Authors Bruno Durand

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_65

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cellular automata (computational aspects) (68Q80)

Recommendations

• A Random NP-complete problem for inversion of 2D cellular automata
• scientific article; zbMATH DE number 4074491
• The reversibility problem for a family of two-dimensional cellular automata
• Invertible cellular automata: A review
• On invertible and stably reversible non-uniform cellular automata
• scientific article; zbMATH DE number 176951
• Intractable problems in reversible cellular automata
• Automata, Languages and Programming

Cited in

(1)

• A Random NP-complete problem for inversion of 2D cellular automata

This page was built for publication: A random NP-complete problem for inversion of 2D cellular automata

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