All Questions
Tagged with cellular-automata np-complete
3 questions
5
votes
0
answers
80
views
Complexity of still life extentions in Game of Life
The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
- 51
5
votes
1
answer
216
views
What does Cellular Automata Pre-image problem actually means?
I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata.
In the 2nd page he lists three NP-Complete ...
- 143
3
votes
1
answer
304
views
Complexity of $n \times \log n$ tiling problem
Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?
For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a ...
- 139