Affordable Access

The Power of Spreadsheet Computations

Authors
  • Tyszkiewicz, Jerzy
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.

Report this publication

Statistics

Seen <100 times