# The Power of Spreadsheet Computations

- Authors
- Type
- Preprint
- Publication Date
- Jul 27, 2013
- Submission Date
- Jul 27, 2013
- Identifiers
- arXiv ID: 1307.7261
- Source
- arXiv
- License
- Yellow
- External links

## Abstract

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.