I think the challenge is more of a quest to find a way to compute it in less than O(n). The proof for that would just be a working algorithm.

IIRC cellular automaton are Turing-complete? We have proven we can implement simulations of 3d rotational symmetry using regular computers, so that one is straightforward, isn't it?