Complex Systems

Evaluating the Complexity of Mathematical Problems: Part 2 Download 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 .