# Towards understanding the predictability of stock markets from the perspective of computational complexity

James Aspnes, David F. Fischer, Michael J. Fischer, Ming-Yang Kao, and Alok Kumar.
Towards understanding the predictability of stock markets from the perspective of computational complexity.
*Twelfth Annual
ACM-SIAM Symposium on Discrete Algorithms*, January 2001, pp. 745–754.
Available as arXiv:cs.CE/0010021.

## Abstract

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 promise-BCPP, where
P^{NP[O(log N)]}
<=
promise-BCPP
<=
CPP
=
PP. These computational
completeness results open up a novel possibility that the price graph
of a actual stock could be sufficiently deterministic for various
prediction goals but appear random to all polynomial-time prediction
algorithms.

## BibTeX

Download@inproceedings(AspnesFFKK2001,
title="Towards understanding the predictability of stock markets from the perspective of computational complexity",
author="James Aspnes and David F. Fischer and Michael J. Fischer and Ming-Yang Kao and Alok Kumar",
booktitle="Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms",
month=jan,
year=2001,
pages={745--754}
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page