Complex Systems

Evaluating the Complexity of Mathematical Problems: Part 2Download PDF

Cristian S. Calude
University of Auckland, New Zealand

Elena Calude
Massey University at Albany, New Zealand


In this paper we present an implementation of the computational method in [1] that allows ranking mathematical statements by their complexity. We introduce the complexity classes , and, accordingly, show that Legendre's conjecture, Fermat's last theorem, and Goldbach's conjecture are in , Dyson's conjecture is in , the Riemann hypothesis is in , and the four color theorem is in .