I doodled some stuff last night and came to the conclusion that the
proof of Moore and Robson can easily be modified to concern gel. That is when we assume we have a lone swordsman with access to all gel borders (via tunnels or clone potions or whatever) and no worries about the gel babies the problem of deciding whether the gel can be destroyed is NP-hard (with respect to the size of the gel blob).
The reduction of Moore and Robson to 1-in-3-SAT fails in Figures 9 and 10 because of the possibility to remove blobs with 2 eclosed corners diagonally (with 2 empty corners), but new constructions without this problem were easy enough to come up with (attached picture).
In fact, unlike with L-trominoes only (it seems), it was possible to make a NOT-gate too (also in the attached picture). Unfortunately, I could not invent any other logical gates to be able to use the nicer proof of reducting the problem to Boolean satisfiability directly, like Moore and Robson did with L-trominoes and 2x2-blocks. EDIT: Silly me, New Figure 10 is in fact an OR-gate if we label two wires as input wires and the third one as an output wire and take into account that the direction of "
current"
changes. EDIT OF EDIT: No it's not, there is no output for two "
true"
:s. New figure 9 is a wire splitter, so we can in fact use the easier proof of reducing to Boolean sitisfiablity in the case of gel. Appartently the problem with L-trominoes only was not the logical gates, but the variable node, which can easily be made with gel, like this:
.......
....*..
...***.
.***...
**.....
.......
As for the case of domino tilings, the link earlier assumed that the number of holes is bounded. Moore and Robson remark that the number domino tilings can be reduced to the determinant of some "
modified adjancency matrix"
([18],[19]), thus making solvability a polynomial time problem (but maybe not n*log(n) as in your (adS's) link with the bounded number of holes perhaps? EDIT: detecting non-zero determinant has complexity O(n^3) so the earlier link beats the matrix point of view.).
-Kallor
____________________________
Kallor
[Last edited by Kallor at 05-26-2014 07:24 AM]
