  This paper initiates a study into the century-old issue of market
predictability from the perspective of computational complexity. We develop a
simple agent-based model for a stock market where the agents are traders
equipped with simple trading strategies, and their trades together determine
the stock prices. Computer simulations show that a basic case of this model is
already capable of generating price graphs which are visually similar to the
recent price movements of high tech stocks. In the general model, we prove that
if there are a large number of traders but they employ a relatively small
number of strategies, then there is a polynomial-time algorithm for predicting
future price movements with high accuracy. On the other hand, if the number of
strategies is large, market prediction becomes complete in two new
computational complexity classes CPP and BCPP, which are between P^NP[O(log n)]
and PP. These computational completeness results open up a novel possibility
that the price graph of an actual stock could be sufficiently deterministic for
various prediction goals but appear random to all polynomial-time prediction
algorithms.
