  We investigate the expressive power of spreadsheets. We consider spreadsheets
which contain only formulas, and assume that they are small templates, which
can be filled to a larger area of the grid to process input data of variable
size. Therefore we can compare them to well-known machine models of
computation. We consider a number of classes of spreadsheets defined by
restrictions on their reference structure. Two of the classes correspond
closely to parallel complexity classes: we prove a direct correspondence
between the dimensions of the spreadsheet and amount of hardware and time used
by a parallel computer to compute the same function. As a tool, we produce
spreadsheets which are universal in these classes, i.e. can emulate any other
spreadsheet from them. In other cases we implement in the spreadsheets in
question instances of a polynomial-time complete problem, which indicates that
the the spreadsheets are unlikely to have efficient parallel evaluation
algorithms. Thus we get a picture how the computational power of spreadsheets
depends on their dimensions and structure of references.

Programming Languages