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