A Random NP-complete problem for inversion of 2D cellular automata
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 21231 (Why is no real title available?)
- scientific article; zbMATH DE number 522847 (Why is no real title available?)
- scientific article; zbMATH DE number 3205673 (Why is no real title available?)
- Average Case Complete Problems
- Average case completeness
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Inversion of 2D cellular automata: Some complexity results
- Invertible cellular automata: A review
- Matrix Transformation Is Complete for the Average Case
- Randomizing Reductions of Search Problems
- Reversibility and surjectivity problems of cellular automata
- Reversibility of 2D cellular automata is undecidable
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Tesselations with local transformations
- The NP-completeness column: An ongoing guide
- The surjectivity problem for 2D cellular automata
- The undecidability of the domino problem
- Undecidability and nonperiodicity for tilings of the plane
Cited in
(6)- Complexity of inferring local transition functions of discrete dynamical systems
- scientific article; zbMATH DE number 4058875 (Why is no real title available?)
- Tilings: recursivity and regularity
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- On the complexity of deadlock detection in families of planar nets
- 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 Q672376)
