Co-NP-completeness of finite-support Gardens of Eden and rectangular orphans
Co-NP-completeness of finite-support Gardens of Eden and rectangular orphans
For the Game of Life, consider finite-support Gardens of Eden and rectangular orphans, with the encodings specified in the paper and polynomial-time many-one reductions. Co-NP-completeness conjecture. Finite-support Gardens of Eden and rectangular orphans are co-NP-complete. The paper establishes a polynomial-time reduction from finite-support Gardens of Eden to orphans but does not provide a converse reduction, so the claimed completeness remains open.
Sources & referencesView supporting material
Primary source
Ville Salo and Ilkka Törmä, “Gardens of Eden in the Game of Life”, arXiv:1912.00692 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.