The Complexity of Riemann’s Hypothesis

Elena Calude

In this paper we obtain a significantly better upper bound on the complexity of the Riemann’s Hypothesis in [3] by improving the universal register machine language used as well as the optimisation technique. In particular, we prove that the Riemann Hypothesis is in the complexity class CU,3 while the Four Colour Theorem is in CU,4.

Keywords: Riemann’s Hypothesis, Π1 statement, register machine

Fulltext (IP)