Inductive Complexity Measures for Mathematical Problems

Abstract

An algorithmic uniform method to measure the complexity of statements of finitely refutable statements [6, 7, 8], was used to classify famous/ interesting mathematical statements like Fermat’s last theorem, Hilbert’s tenth problem, the four colour theorem, the Riemann hypothesis, [9, 13, 14]. Working with inductive Turing machines of various orders [1] instead of classical computations, we propose a class of inductive complexity measures and inductive complexity classes for mathematical statements which generalise the previous method. In particular, the new method is capable to classify statements of the form ∀n∃m R(n,m), where R(n,m) is a computable binary predicate. As illustrations, we evaluate the inductive complexity of the Collatz conjecture or twin prime conjecture—which cannot not be evaluated with the original method.