A New Measure of the Difficulty of Problems
Cristian S. Calude, Elena Calude and Michael J. Dinneen
Guessing the degree of difficulty of a problem before seeing its solution is notoriously hard not only for beginners, but also for the most experienced professionals. Can we develop a method to evaluate, in some objective way, the difficulty of an open problem? This note proposes such a measure which can be used for a fairly large class of finitely refutable conjectures which includes, for example, Riemann Hypothesis and the Goldbach’s Conjecture. According to our measure, Riemann Hypothesis is more complex than Goldbach’s Conjecture. We also show, in a non-constructive way, that the Collatz 3x +1 Problem is finitely refutable; consequently, our method cannot be applied, hence stronger versions of this problem are studied.