A Random NP-complete problem for inversion of 2D cellular automata
From MaRDI portal
Publication:672376
DOI10.1016/0304-3975(94)00293-RzbMath0873.68140OpenAlexW1980104174MaRDI QIDQ672376
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00293-r
Related Items
Tilings: recursivity and regularity, Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems, On the complexity of deadlock detection in families of planar nets, Inferring local transition functions of discrete dynamical systems from observations of system behavior
Cites Work
- Reversibility of 2D cellular automata is undecidable
- Invertible cellular automata: A review
- Average case completeness
- Reversibility and surjectivity problems of cellular automata
- Inversion of 2D cellular automata: Some complexity results
- The surjectivity problem for 2D cellular automata
- Undecidability and nonperiodicity for tilings of the plane
- Tesselations with local transformations
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Randomizing Reductions of Search Problems
- Average Case Complete Problems
- Matrix Transformation Is Complete for the Average Case
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- The undecidability of the domino problem
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
