infidel@maths.uwa.oz.au (INFIDEL) (03/11/91)
I'm looking for any proofs showing that, say, certain 1-d CA are in the class NP; i.e. complexity results about CA. I know that J. von Neumann showed that the 2-d CA (Game of Life) is universal; I've also read about analytical results by Odlyzko et. al. showing how future states of certain "linear" 1-d CA can be calculated in advance without having to go through the iterations. I heard a rumour that S Wolfram started a journal on CA; unfortunately, out in the wilderness over here (Perth, Western Australia) we have to rely on international pidgeon post for our journals --- so I don't know if Wolfram's journal is dinkum. I'd be grateful if a voice out yonder could confirm that the journal exists; and if it does, if they could provide some contact address for it. Finally, if anyone's heard of any connections between NP and CA, holler out so's I can hear ya! John Wojdylo Department of Mathematics University of Western Australia Perth Nice place, really.