• computability theory
• computational complexity theory
• measurement theory
• philosophy of mathematics

The thesis aims to analyze some fundamental theoretical elements of Computability Theory and Computational Complexity Theory such as "degree/measure of difficulty (or complexity)", "reduction", "efficiency", "intrinsic difficulty (complexity)". Often one can read statements such as: "Turing-reducibility allows us to measure the degree of difficulty of a certain mathematical problem " or "The complexity classes provide a measure of the complexity of a certain problem ". To what extent we can consider these statements meaningful? A first question that can be asked is: can we measure (in the sense of Measurement Theory) the difficulty and complexity of a mathematical problem? The aim of the thesis is also to show how the answer to this question can provide interesting conceptual clarifications of the aforementioned theoretical elements. Regarding the notion of efficiency, it seems that it should play a role of great importance within Computational Complexity, however, its characterization in terms of polynomial complexity is very controversial and often considered unsatisfactory. Consequently, the thesis aimed to provide an alternative characterization of the notion of efficiency within Computational Complexity.