What links are there between CA and complexity theory?
See: Juris Hartmanis. On the Computing Paradigm and Computational Complexity. MFCS’95. (eds.) J.Wiederman, P.Hajek. Berlin, Springer 1995, LNCS No.969, pp. 82- 92. In this paper you will find an overview of the state of affairs in computational complexity theory. Note that the author is probably No.1 world authority in the subject. The paper includes also an interesting disscussion of recent Adleman’s molecular solution of the Hamiltonian path problem. The conclusion is that even molecular computations can not escape the exponential curse. The weight of “soup” becomes prohibitive. The calculations show that for a graph with 200 nodes the biologically encoded set of paths will weight more than the Earth ! The exponential function grows too fast and even atoms are a bit too heavy to break this barrier. There is also another worthwhile paper: 3) Paul Vitanyi Physics and the New Computation MFCS’95. (eds.) J.Wiedermann, P.Hajek. Berlin, Springer 1995, LNCS 969, pp. 106-128. It discusses th
