Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


[Computational complexity of] finding outcomes

If one sets up a function to compute the outcome after t steps of evolution from some fixed initial condition—say a single black cell in a cellular automaton—then the input to this function need contain only Log[2,t] digits. But if the evolution is computationally irreducible then to find its outcome will involve explicitly following each of its t steps—thereby effectively finding results for each of the 2^Log[2,t] possible arrangements of digits corresponding to numbers less than t. Note that the computation that is involved is not necessarily in either NP or PSPACE.


From Stephen Wolfram: A New Kind of Science [citation]