Complex Systems

Evaluating the Complexity of Mathematical Problems: Part 1 Download PDF

Cristian S. Calude
University of Auckland, New Zealand

Elena Calude
Massey University at Albany, New Zealand


In this paper we provide a computational method for evaluating the complexity of a large class of mathematical problems in a uniform way. The method, which is inspired by A New Kind of Science [1], is based on the possibility of completely describing complex mathematical problems, such as the Riemann hypothesis, in terms of very simple programs. The method is illustrated on a variety of examples from different areas of mathematics and its power and limits are studied.