Determine Whether a Still Life Pattern is Strict in Polynomial Time

[g0t0]

Lifewiki says:

It has been shown that it is possible to determine whether a still life pattern is a strict still life or a pseudo still life in polynomial time by searching for cycles in an associated skew-symmetric graph.

However, I can't see the algorithm in the 2 references below.

What is the algorithm?

[NooneAtAll3]

there's a mention in https://en.wikipedia.org/wiki/Skew-symmetric_graph

Cook (2003) shows that a still life pattern in Conway's Game of Life may be partitioned into two smaller still lifes if and only if an associated switch graph contains a regular cycle. As he shows, for switch graphs with at most three edges per vertex, this may be tested in polynomial time by repeatedly removing bridges (edges the removal of which disconnects the graph) and vertices at which all edges belong to a single partition until no more such simplifications may be performed. If the result is an empty graph, there is no regular cycle; otherwise, a regular cycle may be found in any remaining bridgeless component. The repeated search for bridges in this algorithm may be performed efficiently using a dynamic graph algorithm of Thorup (2000).

Dunno what "associated switch graph" means here

---

I also found https://www.paradise.caltech.edu/~cook/ ... heory.html which I think are Cook's lecture notes from '98(?), where he wrote

exactly two subsets (the standard definition) -- O(n^2)
two or three subsets -- NP-complete
two or three or four subsets (i.e. any number of subsets) -- [open problem]

(I think NP-completeness comes from map 3-coloring being NP-complete)
(Edit: I was wrong)

---

By the way, where did you find the referenced book?

----

Sooooo I spent some time downloading the book from Anna's Archive,

In section 3 we will propose a natural modification of the definition to allow partitioning patterns into any number of sets of islands, rather than just two
...
In section 5 we will show that the problem of testing patterns according to modified definition in section 3 is, in fact, NP-complete as well

so I guess no poly

----

O(n^2) algo in the paper is the same as at https://www.paradise.caltech.edu/~cook/ ... dPoly.html
To me it feels like it builds abstraction on the wrong layer (GoL cells instead of graphs made from island boundaries), so can be simplified in presentation somewhat

[g0t0]

exactly two subsets (the standard definition) -- O(n^2)
two or three subsets -- NP-complete
two or three or four subsets (i.e. any number of subsets) -- [open problem]

For Lifewiki definition(two or three or four subsets), it's an open problem, so why it is possible to determine whether a still life pattern is a strict still life or a pseudo still life in polynomial time?

Can someone edit it?

Edit: Oh, it is NPC, not open problem.

Edit:
I can't read the book.(May cause of great firewall.)

[NooneAtAll3]

Edit:
I can't read the book.(May cause of great firewall.)

Forum filters by file extension, of all things
Rename into .pdf before opening

Still_Live_Theory_Cook_2003.rle

rename to .pdf

(6.68 MiB) Downloaded 1 time

----

I think there's mistake in 3-sets-NPC
Wire turn doesn't work

Code: Select all

x = 20, y = 18, rule = B3/S23
2b2o$2bo$3bo12b2o$4bo10bobo$5bo3b2o3bo$6bobobo2bo$7b2obobo$11bo4$2o$o
17b2o$bo15bobo$2bo8b2o3bo$3bo8bo2bo$4bobo5bobo$5b2o6bo!

---

I remembered a thing from not so long ago that should work, I think?

Code: Select all

x = 25, y = 16, rule = B3/S23
11bob2o$11b2obo2$11b3o$10bobobo$9bo5bo$8bo7bo$7bo9bo$6bo11bo$5bo13bo$
4bo15bo$3bo17bo$2bo19bo$bo21bo$o23bo$2o21b2o!

Y-connection is still broken, tho

Code: Select all

x = 26, y = 26, rule = B3/S23
$8b2o$8bo$9bo12b2o$10bo10bobo$11bo3b2o3bo$3b2o7bobobo2bo$3bobo7b2obob
o$6bo10bo$7bo10b3o$8bo11bo$9bo8b2o$8b2o8bo$19bo$20bo$21bo$5bo16bobo$5b
3o5b2o8b2o$8bo4bobo$7bobo6bo$6bo2bo7bo$5bo3b2o7bo$2bobo14bo$2b2o14b2o
!

----

nevermind, I misunderstood what connectedness and polyplet means

since turn and Y-connection are king-move-connected, it's all the same island