A Random NP-complete problem for inversion of 2D cellular automata (Q672376)

From MaRDI portal

Jump to:navigation, search

scientific article

In more languages

Language	Label	Description	Also known as
English	A Random NP-complete problem for inversion of 2D cellular automata	scientific article

Statements

scholarly article

A Random NP-complete problem for inversion of 2D cellular automata (English)

zbMATH Open document ID

10.1016/0304-3975(94)00293-R

Theoretical Computer Science

publication date

28 February 1997

Mathematics Subject Classification ID

zbMATH DE Number

zbMATH Keywords

co-RNP-completeness

MaRDI profile type

MaRDI publication profile

Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures

The undecidability of the domino problem

Randomizing Reductions of Search Problems

Matrix Transformation Is Complete for the Average Case

Inversion of 2D cellular automata: Some complexity results

The surjectivity problem for 2D cellular automata

Average case completeness

The NP-completeness column: An ongoing guide

Reversibility of 2D cellular automata is undecidable

Reversibility and surjectivity problems of cellular automata

Average Case Complete Problems

Shorter Note: The Converse of Moore's Garden-of-Eden Theorem

Tesselations with local transformations

Undecidability and nonperiodicity for tilings of the plane

Invertible cellular automata: A review

full work available at URL

https://doi.org/10.1016/0304-3975(94)00293-r

Sitelinks

Mathematics(1 entry)

mardi Publication:672376

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q672376&oldid=37339087"