INDUCTIVE COMPLEXITY MEASURES FOR MATHEMATICAL PROBLEMS
Mark Burgin, Cristian S. Calude, Elena Calude · International Journal of Foundations of Computer Science · 2013
An algorithmic uniform method to measure the complexity of finitely refutable statements [6, 7, 9] was used to classify famous/interesting mathematical statements like Fermat's last theorem, the four colour theorem, and the Riemann hypothesis [8, 15, 16]. 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 Π2–statements. As illustrations, we evaluate the inductive complexity of the Collatz and twin prime conjectures — statements which cannot be evaluated with the original method.