INDUCTIVE COMPLEXITY MEASURES FOR MATHEMATICAL PROBLEMS

Source abstract

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.