On the possibility and limitations of measuring degrees of difficulty, complexity and feasibility of mathematical problems

(1)

Universit`

a di Pisa

DIPARTIMENTO DI CIVILT `A E FORME DEL SAPERE Tesi Magistrale in Filosofia e Forme del Sapere

On the possibility and limitations of measuring degrees of

difficulty, complexity and feasibility of mathematical problems

Candidato:

Filippo Leoni

Relatore:

Prof. Luca Bellotti

Correlatore:

(2)

Aknowledgements

I would like to thank Professor Luca Bellotti and Professor Walter Dean who helped me, with perseverance and openness, by improving the thesis with their suggestions and pointing out errors. I am also grateful to my parents who have always supported me during these years. Last, but not least, I want to thank Irene for being close to me over these years.

(3)

Introduction

The thesis here presented is aimed at addressing some theoretical issues concern-ing Computability Theory and Computational Complexity Theory. In particular, the thesis aims to thematize and develop some theoretical issues formulated by Dean1 _{regarding some central concepts of the aforementioned theories. Indeed,}

concepts as "dicult", "complex", "measure", "degrees", "feasible" are often used by mathematicians and philosophers of mathematics without carrying an in-depth analysis of the latter. Some examples of this situation are furnished by the follow-ing quotations:

Given an algorithmically unsolvable problem X, one associates to X a degree of unsolvability, i.e., a quantity which measures the amount of algorithmic unsolvability which is inherent in X.

[Simpson 2015]

We can think of X ≤T Y2, as meaning that X is at least as easy

to compute as Y . Then X ≡T Y means that X and Y are equally

easy to compute. Thus the degree of X is a measure of the diculty of computing Y ; the higher this degree (in the partially ordered set of degrees), the more dicult Y is to compute.

[Shoeneld 1971]

We can see from these two quotations that some relations among problems in Computability Theory are seen as measuring the intrinsic diculty of a problem. What happens if we treat rigorously these statements? Measurements practice has

1_{Professor Dean's personal communication, see also [Dean 2018].} 2_X _{is Turing reducible to Y , A/N.}

(6)

some precise features and standards: it is not obvious that they can be applied to Computability Theory. Moreover, we will see that answering these questions will provide a theoretical clarication about the status of notions such as "reduction" and "easier/harder than". In particular, we will try to understand what is the notion of diculty involved in Computability Theory and how we can measure it. It will turn out that this notion is strictly related to the notion of reduc-tion. Consequently, it seems that we should be very careful in talking about "intrinsic diculty" since the latter can change as the type of reduction involved changes. Furthermore, it seems natural asking whether the same consideration can be extended to Computational Complexity Theory in which most of the features of Computability are involved; especially since we can easily nd considerations about Computational Complexity like the following:

For some interesting problems it is useful to consider classes within P and particularly the seemingly smaller space classes of deterministic log space, denoted L, and nondeterministic log space, denoted NL. These classes provide a measure with which to distinguish between some interesting problems within P, and present interesting issues in their own right.

[Fortnow and Homer 2002]

The quotation presents an interesting perspective: complexity classes provide a measure of complexity. Moreover, according to the authors, it is worth to con-sider new complexity classes to have a more detailed measure. Consequently, it is natural asking whether this analogy with measurement is signicant and whether, through Computational Complexity, we are measuring complexity in a theoret-ically satisfactory way. However, there is one new aspect to consider regarding Computational Complexity: feasibility. Indeed, Computational Complexity aims to characterize the notion of "ecient solvable problem". In the name of mathe-matical rigour, feasibility is characterized as polynomial running time. However, there is often a feeling of dissatisfaction regarding this point as the following pas-sage shows:

The discussion above shows that the crude classication of feasible computability in terms of polynomial upper bounds on almost every

(7)

input misses the mark. Practical computability is concerned with the behaviour of specic algorithms, running well (but not necessarily in polynomial time on almost all inputs) on specic machines (certainly not Turing machines) and on nitely many inputs of a specic structure (not necessarily captured by a purely numerical bound on the length of their representation). The concerns of feasible computability are thus orthogonal to those of Complexity Theory. The latter should be taken as a study that tells us a lot about the abstract world of the recursive functions, but little about real-life issues concerning compu-tations. Nevertheless, [...] the notion of polynomial time computability has more than sucient motivations [...] to deserve a thorough math-ematical study, disregarding its connections with feasibility, which are seen here as a distraction.

[Odifreddi 1999]

It is worth to analyze this quotation since it contains a lot of interesting causes for reection. We can summarize in a few points some aspects that will be relevant in our discussion:

The quotation gives us some hints about our intuitions regarding feasibil-ity: specic algorithms that run well on specic machines and nitely many inputs. These intuitions are very important to treat feasibility.

Since it is very unlikely that we can treat these conditions formally, consid-erations about feasibility should be abandoned.

The notion of polynomial time computability has great importance in com-plexity and it is worth to study regardless of its connection with the notion of feasibility.

The connection between feasibility and polynomial time computability is too obscure and hence we can see it, inside a formal presentation of Computa-tional Complexity, as a distraction.

These points will be our starting point to analyze the notion of feasibility: we will deal with our intuitions about feasibility trying to understand what are the

(8)

diculties connected with it. Moreover, we will argue that the connection be-tween feasibility and polynomial computability is not a distraction but captures some important practical facts. However, we will claim that this characteriza-tion is incomplete and still unsatisfactory from both a theoretical and practical perspective.

It is worth to emphasize that all these issues are not simply terminological questions. Indeed, the analysis that we will carry out will provide some important theoretical clarications inside the three theories that are objects of our reections. The thesis is organized as follows: the rst chapter is devoted to introducing technically Computability Theory, Computational Complexity and Measurement theory; in the second chapter, we will deal with the analysis of Computability Theory: we aim to understand to what extent we can arm that, through Com-putability we are measuring the diculty of a problem. Moreover, it will turn out that this measure can provide some interesting insight into the structure we are measuring. In the third chapter, we will deal with Computational Complexity Theory. We will follow the considerations of the second chapter and, in addition, we will deal with some of the peculiar problems of Computational Complexity. Our rst aim will be again to understand to what extent we can say that we are measuring the complexity of a problem through Computational Complexity. It will turn out that our empirical structure is still too obscure and also that the measure is not uniform depending on the type of resource we decide to measure. Finally, the fourth chapter is entirely devoted to the analysis of feasibility and to explore the possibility of treating it inside Computational Complexity in a satisfactory way.

(9)

Chapter 1 Computability, Computational

Complexity and Measurement

In this chapter, we will present the logical and mathematical framework of the entire thesis. We will state the main denitions and theorems of three theories: Computability Theory, Computational Complexity Theory and Measurement The-ory that will be the subjects of our investigations in the next chapters. The main features of classical logic will not be object of our discussion, hence the reader is supposed to have some knowledge of these topics.

1.1 Computability theory

In this section, we will give some of the main denitions of Computability Theory. Moreover, we will state some of the main theorems that, although not always connected with the rest of the thesis, should give a general idea of the features and the importance of this theory inside mathematics. It is important to keep in mind that this section is not a general introduction about Computability Theory. Indeed, its aim is only instrumental to the developments of the topics of research of the thesis.

(10)

1.1.1 Basic denitions

We introduce one of the most important formalisms that are crucial to under-standing the developments of Computability and Computational Complexity: Denition 1.1.1 (Turing Machine). A Turing Machine M is a quadruple

M = hQ, Σ, δ, q0i

where:

Q is a nite set of states. Σ is a nite set of symbols. q0 ∈ Q is the initial state.

δ ⊆ (Q × Σ) × (Q ∪ {h} × Σ × {L, R, −} is the transition relation, where h /∈ Q is the halting state and {L, R, −} are, respectively, the directions "left", "right" and "don't move".

A conguration of a Turing Machine is a quadruple (q, u, σ, v), q ∈ Q and u, v ∈ Σ∗

where Σ∗ _{is the set of all the strings with alphabet Σ; u, v are, respectively, the string}

on the left and the string on the right of σ ∈ Σ.

A function f(~x) is said Turing-computable if and only if there exits a Turing Machine M that starting from the intial conguration (q0, u, ~x, v), following the

transition relation, halts in the conguaration (h, u, f(~x), v).

The following denition gives us another fundamental formalism to grasp the main aspects of Computability Theory.

Denition 1.1.2 (Primitive recursive function). The class of the primitive recur-sive functions is the smallest class of functions such that:

1. It contains the following initial function: (a) The costant function Zero(x) = 0; (b) The successor funtion S(x) = x + 1;

(11)

(c) The projection function P rojn

i(x1, . . . , xn) = xi,1 ≤ i ≤ n ∈ N.

2. It is closed under the following operations:

(a) Substitution, i.e, if g1, . . . , gn, h are primitive recursive functions, then

also f dened as

f(~x) = h(g1(~x), . . . , gn(~x))

is a primitive recursive function;

(b) Recursion schema, i.e, given g, h both primitive recursive, then also f dined as

f(~x, 0) = g(~x)

f(~x, S(y)) = h(~x, y, f (~x, y)) is primitive recursive.

It is worth to point out that Turing Machines and primitive recursive functions are two formalisms apt to capture our intuitions about what is computable, i.e, what is a mechanical procedure suitable for resolving a class of problems. There are also other possible formalism, such as λ-calculus, that are able to formalize our intuitions about computability, however, they will be not of central interest in our discussion, hence, they are not treated here. We will see further on that all these formalisms can be considered as equivalent. We now continue the series of denitions.

Denition 1.1.3. A function f is dened from a predicate R by µ-recursion, or minimization, if and only if:

1. ∀~x∃yR(~x, y);

2. f(~x) = µyR(~x, y) where µy is the smallest y such that R(~x, y) is valid. Furthermore, f is dined by minimization by the function g if and only if:

1. ∀~x∃y(g(~x, y) = 0); 2. f(~x) = µy(g(~x, y) = 0).

(12)

Combining the above denitions, we can nally state the denition of the class of recursive functions: it is the smallest class which contains the initial fucntion and that is closed under substitution, recursion schema and minimization. We can now dene when a predicate is recursive:

Denition 1.1.4. A predicate P is recursive if and only if its characteristic func-tion: χP(~x) =    1 if P (~x) 0 otherwise is recursive.

We now deal with the notion of partial recursive function: the idea is that a function can be undened under certain arguments. We will use greek letters to denote partial functions. The notation φ(~x) ↓ means that φ is dened (converges) on ~x. The formal denition of the class partial functions is similar to the denition of the class of recursive functions, the only dierence is the schema of minimization:

φ(~x) = 





µy[∀z < yψ(~x, z) ↓ ∧ψ(~x, y) = 0] if such y exists undened otherwise

We now state one of the most important conjecture in Computability, the so called "Church-Turing Thesis"(CT T ):

CTT: The fuction eectively computable are exactly the recursive functions. Since it is possible to show that the recursive fuctions are Turing-computable [Davis 2004] CTT can be restate with Turing computability rather than recurisive functions. The thesis arms the non trivial fact that the formalism of recursive functions capture precisely our intuitions about eective procedures. It is not the aim of this thesis to discuss CTT. The reader can see the the deticated section in [Bellotti et al.] to nd the relevant leterature.

1.1.2 Normal Form Theorem

This result, although not directly connected with our topics of investigation, can not be omitted, in author's opinion, in any presentation, even very incomplete like

(13)

this one, of Computability Theory.

Theorem 1.1.1 (S. Kleene 2004a). For all k ∈ N there exists a recursive predicate Tk(e, ~x, y) and a primitive recursive function U(x) such that:

φ(~x) = U (µyTk(e, ~x, y))

The proof is quite long and complex, consequently we only give a brief outline to x the main ideas. For further details see [Bellotti et al. 2001].

1. First of all, we need to encode recursive functions. To do that, we proceed in the style of Gödel numbering: we use the fundamental theorem of arith-metic to assign numbers to the initial functions and we give rules to assign numbers to the functions obtained by substitution, recursion schema and minimization. This number is called the index of the function.

2. We now need to assign numbers to computations. To to that, we repre-sent them as computation trees where the nodes without predecessor that correspond to the initial functions. If f(~x) was obtained by substitution, then he will have m + 1 nodes which are labeled, respectively, with h1(~x) =

z1, . . . , hm(~x) = zm and with g(z1, . . . , zm) = z. An analogue reasoning can

be carried out for the other operations. We can now assign numbers by in-duction on the computation tree since the nodes correspond to expression of the form f(~x) = z we can code each node as heh~xizi and, eventually, we can assign to each tree a number by induction on the size of the trees.

3. We build a recursive predicate T (y) which witnesses that y is a number that encodes a computation tree. This is the longest part of the proof and it is here omitted. What we have to do is to construct T so that it expresses, using only primitive recursive predicates, all the properties considered in points 1 and 2 above.

4. We can now dene U as a function that extracts the results of the computa-tion from its encoding ,i.e, the y of point 3. Consequently, U can be seen as a projection function and, hence, is primitive recursive. This ends the proof, since, given a recursive function f with arguments x1, . . . , xn and index e,

(14)

there exists a computation tree encoded by Tk(e, ~x, y). Moreover, from each

tree, starting with the one that has the smallest code, we can extract the value of the function simply extracting, with U, the right component from the sequence that code the computation.

We can say that this theorem constitues the foundations of Computability Theory since it provides a general explanation of what is a computation, i.e, it furnishes a universal abstract model of the process of computing. Moreover, note that the rst step allows us to assign a natural number to every recursive function which we use as an index. Consequently, we can say that only the functions in the enumeration, i.e, the functions with an index are recursive.

1.1.3 Recursively enumerable set

Denition 1.1.5. A set is recurively enumerable (r.e) if and only if it is the domain of a partial function.

Consider the following set:

K = {x|φx(x) ↓}

It is very simple to show that this set is r.e. Indeed K is the domain of the following partial function: ψ(x) =    x if φx(x) ↓ undened otherwise We now show that K is not recursive:

Proposition 1.1.1 (Turing 1937). K is not recursive.

Proof. For the sake of contradiction, suppose χkis recursive, then also the following

function is recursive: f(x) =    φx(x) + 1 if x ∈ K 0 if x /∈ K

We immidiately obtain a contradiction since ∀xf(x) 6= φx(x), i.e, f has not an

(15)

The following theorem will permit to show that K the complement of K, is non-r.e.

Theorem 1.1.2 (E. Post 2004). A set A is recursive if and only if both A and A are r.e.

Proof. The only intersting part is the direction from right to left: let φi and φi

be, respectively, the semi-characteristic of A and A. We ca now use the following procedure: give any x run φi(x) if φi(x) ↓ then x ∈ A, otherwise run φi, if φi ↓,

then x /∈ A. Thanks to this procedure, we can dene the recursive charcteristic function of A, i.e, A is recursive.

It follows that K can not be r.e, otherwise K would be recursive which is a contradiction. We thus established a fragment of a hierarchy:

R ⊂ RE ⊂ nonRE

namely, the recursive sets are a proper subset of r.e sets which are a proper subset of non r.e sets. This fact will be the starting point of the next section.

1.2 Reducibilities and Degrees

The topics of this section are relative computability and the notion of reduction. These two concept will be central in the rest of the thesis. The key idea is the following: suppose you are trying to solve a problem A. You have two possibilities: you directly solve A or, in case you aren't able to solve it, yuo can trasform it into another problem for which you already know a solution. We now give some denitions that make rigorous this idea.

1.2.1 Many-one degrees

Denition 1.2.1 (many-one reducibility). Given two sets A, B ⊆ N, A is said to be many-one reducible to B if there is a recursive function f(x) such that for all n ∈ N:

(16)

In this case we write A ≤m B.

The importance of this tool is given by the following classical example. Consider the set

HP = {(x, y)|φy(x) ↓}

HP is the halting problem: given a program and an input, does the program halt on the given input? There is a trivial reduction from K to HP , i.e, x ∈ K if and only if (x, x) ∈ HP , hence HP is not recursive (note that the reduction function is simply the pairing function). It is a natural to ask what is the hardest problem of a given class of sets. Such a problem is said to be complete for the class in question.

Denition 1.2.2. A set B is said to be many-one complete for the class E if and only if:

B ∈ E;

For all sets A ∈ E, A ≤m B.

Denition 1.2.3. Given A, B ⊆ N if A ≤m B and B ≤m A, then A is said to be

many-one equivalent to B, formally A ≡m B.

It follows immidiatly form the denition of many-one reducibility that this relation is riexive. It is also transitive, since if f reduces A to B and g reduces B to C, then f ◦ g reduces A to C. Furthermore, it symmestric by denition. Consequently, ≡m is an equivalence relation. Therefore, we can dene equivalence

classes with respect to it.

Denition 1.2.4. degm(A), the many-one degree (m-degree) of A, is the

equiva-lence classes of A with respect to ≡m.

We denote m-degrees with boldface low case Roman letters a,b etc. We next dene an ordering on m-degrees:

Denition 1.2.5. Let a,b be m-degrees. We dene:

(17)

a <m b if and only if a ≤m b and a 6= b.

We can nally dene the structure of m-degrees: Dm = h{degm(A)|A ⊆ N}, <mi

Note that Dm is a partially ordered structure since <m is irriexive, antysimmetric

and transitive (it follows directely from the dinitions).

1.2.2 Turing degrees

The key idea of Turing reducibility is the notion of oracle Turing Machine. An oracle Turing machine is a normal Turing Machine plus an oracle tape on which is written the characteristic function of a given problem, say B. The intuition behind this formalism is that a problem A is reducible to B, if, given a solution to B, we can solve A. Consequently, the transitions of an oracle Turing Machine solving A, are determined by its internal state together with both the symbols scanned in its reading tape and oracle tape. The idea is that the machine, to solve A, consult an oracle. The following is the formal denition:

Denition 1.2.6. Given two set A, B ⊆ N, A is said to be Turing reducible (T-reducible) to B, if there is an oracle machine computing the characteristic function of A using the characteristic function of B. In this case we write A ≤T B.

The denitions of T -complete problem, T -equivalence (≡T) and T -degree are

the same of the previous section substituting ≤m with ≤T. Also the structure of

T-degrees, denoted by DT = h{degT(A)|A ⊆ N}, <Ti, is dened in the same way

and is a partial order. We can see that T -degrees, as well as m-degrees are able to classify problems by their diculty retracing the fragment of hierarchy we have shown at the end of Section 1.1.3.

We now deal with the operation of Turing-jump that will be extremely impor-tant in the next chapter. Consider the set

KA= {x|φA x(x) ↓}

(18)

the so-called diagonal Halting Problem relativized to A. KA is said to be the

Turing jump of A and is denoted by A0_{. We will see in the next section that there}

is a strong relation between Turing jumps and arithmetical degrees.

1.2.3 Arithmetical Hierarchy

In this section, we will deal with the notion of arithmetical expressibility and its connection with Turing degrees. Recall that the language of Peano Arithmetic is LP A = h0, S, +, ×, <i. A rst-order arithmetical formula is built from the language

LP A using logical connectives, quantiers and variables ranging among natural

numbers. Moreover, remember that the standard model of rst-order arithmetic is N = hN, 0N_{, S}N_,₊N_{, ×}N_{, <}N_i _{where the superscript N means that the symbols}

are interpreted in the usual way inside the natural numbers. We say that a LP A

-formula φ(x) denes a set A ⊆ Nk if and only if

A= {(n1, . . . , nk) : N |= φ(n1, . . . , nk)}

For example, the formula ∃x(y = 2x + 1) denes the odd numbers. We are now interested in classifying formulas by their logical complexity, i.e, the nesting of quantiers. This will permits to analyze the diculty of a problem, i.e, a subset of natural numbers, simply looking at the complexity of the formula that denes it.

Denition 1.2.7 (Arithmetical Hierarchy AH). A LP A-formula is said to be ∆0

if and oly if it contains only bounded quantiers, i.e those of the form ∃x(x < t∧...) and ∀x(x < t → ...), for a term t not containing x. A formula is said to be Σ1

if it is of the form ∃xφ(~x, ~y) where φ(~x, ~y) ∈ ∆0. The dention of Π1 is dual. A

formula is said to be ∆1 if it is both Σ1 and Π1. In general we say that a formula

is Σn+1 if it is of the form ∃xφ(~x, ~y) where φ(~x, ~y) ∈ Πn. The class Πn is dened

dually. A formula is said to be ∆n+1 if it is both Σn+1 and Πn+1.

The following proposition state only one of the results that show the important relationship between the classication of arithmetical formulas and Computability Theory.

(19)

Proposition 1.2.1. A relation R ⊆ Nk is r.e if and only if there is a Σ

1-formula

which denes it.

To conclude the section we will state the Post's Theorem. This theorem has many imporant consequences, however, we will be interested only in its conse-quences regarding the possibility of measuring the diculty of a problem, a topic that we will face in the next chapter. Recall that ∅(n) _{is the n-fold iterated Turing}

jump of ∅.

Theorem 1.2.1 (E. Post 2004). 1. A is Σn+1-denable if and only if A is r.e

by an oracle Turing machine with an oracle for a set B Πn-denable if and

only if A is r.e by an oracle Turing machine with an oracle for a set C Σn-denable.

2. A set B is Σn+1 denable if and only if B is r.e by an oracle Turing Machine

with an oracle for ∅(n)

3. Every Σn-denable set is many-one reducible to ∅(n),i.e, ∅(n) is Σn-complete.

The proof of this theorem is inessential to our discussion and it is omitted. Among the corollaries of Post's Theorem we can nd the Kleene's Theorem: Theorem 1.2.2 (S. Kleene 2004b). For all n ≥ 1, there exists a set A ⊆ N which is Πn-denable but not Σn-denable and hence niether Σm- nor Πm-denable, for

every m < n.

We will draw some interesting conclusions from both these theorems regarding the possibility of measuring degrees of unsolvability. As a preliminary considera-tion, note that Kleene's Theorem implies that AH doesn't collapse. Indeed, as a consequence of the well-known Prenex Normal Form Theorem, every LP A-formula

is Σn or Πn for some n ∈ N. Since we allow empty blocks of quantiers in the

denition of AH, it follows that, for all n ∈ N, Σn ⊆ ∆n+1 ⊆ Σn+1. The same is

valid for the class Πn. The above theorem shows that these inclusions are strict.

1.3 Computational Complexity Theory

We can see Computational Complexity theory as a natural development of Com-putability Theory. Indeed, once we succeed to classify problems by their degree

(20)

of unsolvability, we would like to understand how dicult it is to solve solvable problems, i.e, recursive problems, in practice. Hence, we are interested in consid-ering the resources needed to solve a recursive problem and, eventually, we would like to classify recursive problems by their complexity, i.e, by the numbers of steps a Turing machine uses proportionally to the size of the input. We now deal with some formal aspects of this theory. Again, it is important to keep in mind that this is not an introduction to Computational Complexity Theory since we will treat only some of the main developments to give a general idea of the features and the importance of it.

1.3.1 Basic conventions and denitions

The following ponits summarize some of the basic conventions we will deal with for the rest of the chapter:

When we talk about a problem we intend an innite set of instances that serve as inputs for a given algorithm. There exists a function, which depends on the type of problem we are considering, that maps all the instances into the set {0, 1}∗_{, i.e, the set of all the strings with alphabet 0 and 1. Consequently,}

a problem X is considered a subset of {0, 1}∗ _{and is also called "language".}

A language X is decided by an algorithm M just in case M computes its characteristic function.

The size of an instance is given by the function |.| : X → N that depends on the type of problem we are considering.

The function timeM(x)returns the number of steps required for M to halts

on input x. The function tM = max{timeM(x) : |x| = n} returns the

worst-case time complexity of the machine M dened as the maximum number of steps required for M to halts on input x of size n. The same denition can be used to dene worst-case space complexity. Space and time will be the only two resources that we will consider in this thesis.

(21)

Given a function f we dene its order of growth to be

O(f (n)) = {g(n) : ∃c∃n0∀n ≥ n0(g(n) < c × f (n))}

that is the set of all functions that are asymptotically bounded by f.

The time and space complexity of a problem X is given by the worst time and space complexity of the asymptotically most ecient algorithm for deciding X.

Turing machines (see Denition 1.1.1) are the standard model of computation considered in Computational Complexity Theory. We now consider the important dierence between deterministic and non deterministic computations. Formally, the dierence is given by the status of the δ: if it is a function, i.e, to every con-guration it assigns exactly one concon-guration, then, the machine is deterministic. On the contrary, if it is actually a relation, i.e, to any conguration it can assign more then one conguration, then the machine is non-deterministic. The idea is that, if δ is a relation, the current conguration is not uniquely determined by the previous conguration. The following example can explain the dierence between deterministic and non-deterministic Turing machines. The language SAT is the set of all satisable propositional formulas. Consider now the following decision problem: given a propositional formula A, A ∈ SAT ? You can follow two pro-cedure: you can enumerate, for all the subformulas of A, all the possible truth assignments or you can "guess and try", i.e, you can guess a truth assignment and verify if it satises A. This example also shows that non-determinism doesn't enlarge the class of problems we can solve,i.e, a deterministic Turing Machine can simulate the non-deterministic process as it happens in the above example. How-ever, it seems intuitive that the second procedure is much faster than the rst. We will see that the proof of this intuition is the most important open problem in Computational Complexity.

1.3.2 Complexity classes and hierarchy theorems

A complexity class is a set of languages all of which can be decided within a given time or space complexity bound. We now give the denition of the main

(22)

complexity classes to which we will refer in the next chapters.

Denition 1.3.1 (Time complexity classes). The class of problems decid-able in deterministic polynomial time is:

P = [

k≥1

T IM E(nk₎

The class of problems decidable in non-deterministic polynomial time is:

NP = [

k≥1

T IM E(nk)

The class of problems decidable in deterministic exponential time is:

EXP = [

k≥1

T IM E(2nk )

The class of problems decidable in non-deterministic exponential time is:

NEXP = [

k≥1

T IM E(2nk )

Denition 1.3.2 (Space complexity classes). The class of problems decid-able in deterministic logarithmic space is:

L = [

k≥1

SP ACE(log n)

The class of problems decidable in non-deteministic logarithmic space is:

NL = [

k≥1

SP ACE(log n)

The class of problems decidable in deterministc polynomial space is:

PSPACE = [

k≥1

(23)

The class of problems decidabe in non-deterministic polynomial space is:

NPSPACE = [

k≥1

SP ACE(nk₎

The following Hierarchy Theorem will be extremely important in our further discussions:

Theorem 1.3.1 (Arora and Barak 2009). If f is among the functions considered in the above denitions, then:

T IME(f(n)) ⊂ T IME(f(2n + 1)3₎

SP ACE(f(n)) ⊂ SP ACE(f(n) × log f(n))

The proof of the theorem use the same techinique used to show that K is not recursive and is here omitted. The well-known corollaries of this theorem permit to build the following hierarchy:

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP

We know, thanks to the Hierarchy Theorem, that P ⊂ EXP and L ⊂ PSAPCE, hence one of the rst four inclusions must be proper. In particular, we strongly belive that P ⊂ NP since, as already mentioned, it seems that non-deterministic procedures are faster then deteministic ones. We will return on the importance of this open question.

1.3.3 Reductions and completeness

We now present two types of reducibility, Karp reducibility and Cook reducibility, that are analogous to those presented in Section 1.2. The formal denitions of both of them are the same as, respectively, Denition 1.2.1 and Denition 1.2.6. The only dierence is the status of the reduction function for Karp reducibility: it is a recursive polynomial-time computable function, indeed, Karp reducibility is also called polynomial-time many-one reducibility and is denoted with the symbol ≤p

(24)

that the number of calls to the oracle is bounded polynomially. Indeed, Cook re-ducibility is also called polynomial-time Turing rere-ducibility and is denoted with the symbol ≤p

T. For the denition of the notion of completeness for a given complexity

class, see Denition 1.2.2. Many interesting results have been proved about the completeness of several problems for all the mentioned complexity classes. Since these results are very-well known they are here omitted, for sake of brevity (see [Arora and Barak 2009] for further details).

1.3.4 Other complexity classes

Note that, for a deterministic Turing Machine to either accept or reject it suces that there exists a halting computation. As a consequence deterministic complexity classes are said to be closed under complementation, i.e, X is in C if and only if X = {x ∈ {0, 1}∗ _{: x /}_{∈ X}} _{is also in C, where C is a deterministic complexity}

class. If this is the case, we say that C = coC (the class of those problems whose complements are in C). We don't know a priori if this is valid for nondeterministic complexity classes. Indeed, consider an NP-problem like SAT . SAT is the set of contradictory formulas of propositional logic. Thus, φ ∈ SAT if and only if ¬φ ∈ V ALID (the set of all valid propositional formulas). This obsevation provide a reduction from SAT to V ALID, hence, the latter is in coNP. Note that to show that φ ∈ V ALID we need to prove that it is true for all possible truth assignments. It is unclear how the membership of a formula in V ALID can be decided with the "guess and try" procedure we described above (remember that, in that case, the machine guesses only one possible assignment). Indeed, the following is another open problem: are the classes NP and coNP distinct?

1.3.5 The Polynomial Hierarchy

This section discusses the polynomial hierarchy, a generalization of the complexity classes we have seen in the previous sections. The idea is similar to that of the denition of AH:

(25)

in Σp

i if there exists a polynomial-time TM M and a polynomial q such that

x ∈ L ↔ ∃u1 ∈ {0, 1}q(|x|)∀u2 ∈ {0, 1}q(|x|), . . . , Qiui ∈ {0, 1}q(|x|)M(x, u1, . . . , ui) = 1

where Qi is ∀ or ∃ depending on whether i is even or odd repectively.

We say that L is in Πp

i if there exists a polynomial-time TM M and a polynomial

q such that

x ∈ L ↔ ∀u1 ∈ {0, 1}q(|x|)∃u2 ∈ {0, 1}q(|x|), . . . , Qiui ∈ {0, 1}q(|x|)M(x, u1, . . . , ui) = 1

where Qi is ∃ or ∀ depending on whether i is even or odd repectively.

The polynomial hierarchy is the set PH = SiΣ p i.

Note that the above examples about SAT ad V ALID explain why Σp

1 =NP

and Πp

1 =coNP. The following theorem shows some important property of PH:

Theorem 1.3.2. 1. For every i ≥ 1 if Σp i = Π

p

i, then PH = Σ p

i (the hierarchy

collapses to the ith _level).

2. If P = NP, then PH = P.

The proof is omitted, see [Arora and Barak 2009]. This conludes the techni-cal outiline of Computational Complexity Theory. We nally discuss briey the importance of the P vs NP question.

1.4 On the signicance of P vs NP

As Sipser [Sipser 1992] rightly states, the P vs NP question can be considered as a nite version of Hilbert's Entscheidungsproblem. In fact, suppose we want to test whether an assertion has a "short" proof: can we say that this can be done eciently? A rst reference to this issue can be found in a short letter from Gödel to Von Neumann (for an english translation see [Sipser 1992]) . Given a formal system S, writes Gödel, consider the problem of deciding whether a certain formula has a proof consisting of at most n symbols. Such a problem, unlike the Entscheidungsproblem, is clearly decidable, if only by some brute force

(26)

mechanism. However, it is clear that, for a large enough n, this process would take enormous time. However, as Gödel himself points out, proving that there is no better approach to the matter is far from trivial. Such a result would be of great importance, says Gödel in the letter, as it would allow the sorting of eciently solvable problems by discriminating, in this way, problems that are not such. It can easily be seen how, with this formulation, we come close to the question of P vs NP: indeed, as we mentioned, we believe that non-deterministic procedures allow us to solve a certain class of problems faster. We strongly believe that such problems would require exponential time to be solved, if we used only deterministic procedures. Consequently, we are convinced that P and NP detect two class of problems: non-complex problems and complex problems. Moreover, as Aaronson states [Aaronson 2012], paraphrasing in contemporary terms what Gödel wrote, if P = NP were true, whenever a theorem had a proof of reasonable length, we could "nd" such a proof in a reasonable time. This would imply that all the problems we consider complex are actually simple to solve. Although it may seem a desirable scenario, it would make, as the reader can easily imagine, extremely dicult to carry out any cryptographic practice. We will return at the end of our discussion on these considerations.

1.5 Measurement Theory

In this section, we will give a brief introduction to the main purposes and features of Measurement Theory. The following quotation introduces some of the main aspects we will deal with.

When measuring some attribute of a class of objects or events we associate numbers (or other mathematical entities, such as vectors) with the objects in such a way that the properties of the attribute are faithfully represented as numerical properties.

[Krantz et al. 1971]

As the quotation states, there are three main features of the process of measur-ing: a class of objects that we want to measure, a class of mathematical objects and a function that, to each object, assigns a mathematical object "in such a way

(27)

that the properties of the attribute are faithfully represented as numerical prop-erties"[Krantz et al. 1971]. To reach this goal, we need rst to individuate a set of properties on the basis of which we will pursue the assignment of mathematical objects. To explain practically these considerations, we make an example in terms of length measurement. Suppose we want to measure a set of rods. We can indi-vituate a set of properties simply by confronting the rods with each other. Given two rods a and b, we can place them side by side and see if they coincide or if one exceeds the other. We say, respectively, that that they have the same length, or that, say, a is longer than b and we write, respectively, a ≡ b or, say, b ≺ a. Note that two rods can be concatenated and thus we can compare the length of a set of concatenated rods with that of another in the same way we have done for the comparison of two single rods. The concatenation of a and b is denoted a ◦ b. We can nd many properties of length comparison and concatenation of rods, e.g, < is transitive, ◦ is associative, etc. Then, we assign numbers φ(a), φ(b) (where φ is a function from rods to natural numbers) to rods a and b, in such a way that if b ≺ a, then φ(b) < φ(a). The assignments should also respect the properties related to the operation of concatenation. Consequently, we can conclude that one of the fundamental questions regarding the foundations of measurement is about the existence of a function φ that satises certain properties. Therefore, we can say that the function φ should be at least a homomorphism, i.e, a structure-preserving map. A representation theorem asserts that if a given empirical structure sat-ises certain properties, then we can construct a homomorphism into a certain numerical structure. This is the basic formal requirement to have a measure. A second important requirement is the uniqueness theorem. Note that, in measuring something, we can arbitrarily choose an element as unit on which the other as-signments depend. We call this element e; of course φ(e) = 1. Moreover, the ratio φ(a)/φ(e) is uniquely determined and independent from the choice of e. Thus, if φ is constructed with e as unit and φ0 is constructed with e0 as unit, we have

(28)

or, substituting φ(e) = 1 and φ0_{(e) = α, we have}

φ0(a) = αφ(a).

In one expression φ → αφ = φ0_{. The uniqueness theorem expresses the fact that}

a measure is unique up to certain types of transformations, like those expressed above. A classical example is given by the dierent temperature scales. In any temperature measurement, two arbitrary choices are made: the zero point and the unit, consequently the transformation in question is of the form φ → αφ + β. For example, you can obtain Celsius degree form Fahrenheit following the equation C = (5/9)(F − 32).

1.5.1 Level of measurement

Depending on the transformations that we allow, we can individuate dierent types of measurement1_{. Scales in which the only permissible transformation is}

φ(a)/φ(e) = φ0(a)/φ0(e)

are called ratio scales because the ratios of scales values are invariant. Scales in which the only permissible transformation is

φ → αφ+ β

are called interval scales because the ratios of intervals are invariant. Scales in which the only permissible transformation is

φ → αφβ

are called log-interval scales because a logarithmic transformation of such a scale results in an interval scale. Scales in which the only permissible transformation is

φ → f(φ)

1_{For historical reasons we follow the classication of [Stevens 1946]. However there is a debate}

(29)

where f is a monotonic increasing function, are called ordinal scales because only the order is preserved in these transformations. In the following chapters, we will deal mainly with this type of measure for reasons that will be claried in the next chapters.

(30)

Chapter 2 Measuring degrees of unsolvability

In this chapter, we will try to develop the analogy between Computability Theory and Measurement Theory. The rst aim will be to show how it is possible to prove Representation and Uniqueness theorems for Computability theory. This rst step will show that it is possible to formally dene a scale with respect to Computability Theory. The second and more philosophical aim will be to argue that we need some non-trivial result (such as Post's Theorem) inside Computability to use this scale fruitfully. Moreover, we will argue that this construction can furnish some theoretical insight into the structure measured.

2.1 On the concept of diculty

Before facing the problem of formally dening a scale, we need to answer (or at least trying to answer) the following question: what are our intuitions about diculty? Although this question is interesting per se, it has special importance in our discussion. Indeed, answering this question will provide us with some insight into the adequacy of our measurement. First of all, we need to circumscribe the meaning of "dicult", since this adjective is used in many dierent ways in natural language. We are mainly interested in mathematical diculty, i.e, in the diculty of problems that we can formulate in mathematical terms. What does it mean that a mathematical problem is dicult? It is a well-known fact that Computability Theory arose in the frame of the debate about foundations of Mathematics and,

(31)

in particular in the frame of Hilbert's program1_{. Indeed it is from Hilbert's words}

that we can understand better what is the "diculty" we are talking about (italics mine):

It is probably this important fact along with other philosophical reasons that give rise to the conviction (which every mathematician shares, but which no one has as yet supported by a proof) that every denite mathematical problem must necessarily be susceptible of an exact settlement, either in the form of an actual answer to the question asked, or by the proof of the impossibility of its solution and therewith the necessary failure of all attempts.

[Hilbert 1902]

The key point is the notion of actual answer. Given a mathematical problem with the form: "x ∈ A?", we would like to admit only two possible answers: yes or no, "for in mathematics there is no ignorabimus" [Hilbert 1902]. We discovered soon, thanks to negative results achieved by Gödel, Church and Turing, that there are ignoramibus, problems to which we have not an actual answer. In particular, as showed in the rst chapter, there are problems to which we can give, with an eective procedure, a postive answer but not a negative one (such as K) and problems to which we can't neither answer "yes", neither "no" (such as K). We can conclude that these problems have dierent degrees of diculty. Consequently, a measure of diculty, to be adequate, must be able to distinguish, at least, between sets that are, respectively, recursive, recursively enumerable and non-recursively enumerable. These are our fundamental "empirical judgements" about the diculty of a mathematical problem, in the sense that this is what we have established about the diculty in mathematics. In the next two sections, we will show that Computability Theory could be intended in the theoretical frame of Measurement Theory and that this measure is intuitively adequate. Note that this notion of diculty is quite far from our common intuition. Indeed, the latter usually ascribes diculty to propositions correspondig to theorems (e.g, Fermat's theorem), to other mathematical statements, e.g., " it is possible to construct

1_{It is not an aim of this writing deepening historical issues, for a serious treatment of these}

(32)

a circle given three points" or to conjectures rather than to decision problems. This situation depends usually on historical facts, e.g, Goldbach's conjecture is dicult since the community of mathematicians has not yet found a solution to it. However, note that, from the point of view of Computability, the following function is easy to compute, i.e, is primitive recursive:

f(x) =  



1if Goldbach's conjecture is true 0if Goldbach's conjecture is false

This happens because in Computability Theory we are interested in classifying problems according to whether or not a procedure to solve them exists, we are not interested in the implementation of such procedures. Although this situation may appear strange and counterintuitive, we will focus on the notion of problem,i.e, decision problem and on the notion of diculty expressed by Computability since they provide a rigorous logical treatment of the notion of diculty in a general manner, i.e, without dealing with contingent facts, such as the time actually em-ployed to prove or disprove a theorem or a conjecture.

2.2 The empirical structure

To show that we can measure degrees of unsolvability using Computability Theory we have to dene rst the empirical structure we deal with. In particular, we would like to analyze our empirical structure from a mathematical point of view. In the rst chapter, we have seen the objects of Computability Theory, i.e problems (subsets of N), and its main features, e.g reducibility. So, at rst glance, it seems that our empirical structure should be hP (N), ≤Ti. The following fact follows

directly from the denition of ≤T.

Fact 2.2.1. hP (N), ≤Ti is a partially ordered set.

We will now show that this structure is complex. Consequently, we must be very careful in building our measurement. It will turn out that it seems reasonable to restrict ourselves to that subsets of N that are arithmetical (i.e, denable by a rst-order formula in the language of Peano Arithmetic) since this structure is less

(33)

complicated. Since every subset of N has a Turing degree, we will deal, from the rest of the chapter, with the structure (DT, ≤T)(for all the denitions see Section

1.2.2). The following are some classical results that give us some insight into the structure we are talking about.

Denition 2.2.1. A string is a partial function σ : ω → {0, 1} with nite domain.

Theorem 2.2.1 (see Odifreddi 1989). There are two incomparable degrees, i.e, there exits A and B such that A T B and B T A.

Proof. Note that A ≤T B means that A = φBe. The strategy is two break the

two global conditions in the statement of the theorem into innitely many local conditions:

1. R2e : A φBe

2. R2e+1 : B φAe

We will now construct A and B such that A = Ss∈ωσsand B = Ss∈ωτs. Moreover,

we construct each stage in such a way that the two condition above are satised. We begin the costruction by setting σ0 = τ0 = ∅. At stage s + 1 suppose that σs

and τs are given.

if s = 2e, then we satisfy R2e: we dene σs+1(x) = 1 − φBe(x).

if s = 2e + 1, then we satisfy R2e+1: we dene τs+1(x) = 1 − φAe(x).

This theorem tells us that (DT, ≤T) is a non-linear structure. This is quite

problematic since Measurement Theory is built on total orders, i.e sets in which every pair of elements is comparable. As a consequence of this situation, we will deal with Arithmetical Hierarchy (AH henceforth, dened in Chapter One). The reason why this is possible is Post's theorem (see Theorem 1.2.1) which provides

(34)

a link between arithmetical degrees and Turing degrees (dened in Section 1.2.2). Thanks to this important result, we can say that there are Turing degrees to which correspond specic arithmetic degrees. Moreover, Kleene's theorem (see Theorem 1.2.2) is a consequence of Post's theorem and provides a separation result for AH. We will argue later that this is a crucial fact to have a fruitful measurement. Remember that the Arithmetical Hierarchy provides a classication (called Σn or

Πn) to subsets of N via their denability through rst-order formulas in prenex

normal form. Since the classication depends on the alternation of quantier and since empty blocks of quantiers are allowed it follows that, for all n, i ∈ N, Σn⊆

Σn+i. Note that hAH, ⊆i is a linear partial order, because given two arithmetical

degrees they are always comparable under ⊆. We now give a characterization of AH to show that this is the appropriate empirical structure to build the measure we are interested in. We consider the subsets of N (P (N)A henceforth) that are

arithmetical, note that these sets have both a Turing degree and an arithmetical degree. We now want to dene when two sets are equivalent. As we have seen in the rst chapter, two sets A, B can be considered equivalent when they have the same Turing degree (and, by Post's theorem, the same arithmetical degree), i.e, when A ≤T B and B ≤T A. In this case, we will say that A ≡T B. We

have already seen that this is an equivalence relation. We now consider AH to be P_(N)A/ ≡T. Note that using this characterization we lost something, indeed the

structures of T -degrees and m-degrees are much more complex as the following proposition shows:

Proposition 2.2.1 (Odifreddi 1989). The partially ordered structures of T -degrees and m-degrees are upper-semilattices of cardinality 2ℵ0 _{with a least but not a}

max-imal element.

Proof. The least upper bound exists and is induced by the disjoint sum of two set,i.e, A ⊕ B = {2x : x ∈ A} ∪ {2x + 1 : x ∈ B}, hence A ⊕ B is the least uppper bound of A and B. The least elements is the degree 0. For any set B such that B ≤∗ A (≤∗ can be both ≤T and ≤m) there exists φe, e ∈ N (φAe if we deal with

T-degrees) such that B ' φe (resp. φAe) and thus there are at most countably

many sets reducible to A. As a consequence there is a injective map from the degrees to P (N). The degrees hence are at least 2ℵ0_{. They cannot be more than}

(35)

2ℵ0 _{since the map B ∈ P (N) → A ⊕ B is again injective.}

Consequently, we can see that our restriction to AH is really restricting. How-ever, the proposition above poses another problem: as we will see the proof a the Representation Theorem applies on countable structures, hence our restriction is necessary. As we will again point out, these restrictions show that the measure is not able to consider the structure is in entire complexity.

2.3 Representation and Uniqueness Theorems

In the rst chapter, we have seen what are the main aspects of Measurement Theory [Krantz et al. 1971]. In particular, we have explained the theoretical im-portance of Representation and Uniqueness Theorems. In the previous section, we have dened the empirical structure in question. We can nally prove these two important theorems for Computability Theory. Our strategy is the following: we rst prove that hAH, ⊆i is a quasi-series (the denition is provided below), then we prove two more general results, i.e, Rapresentation and Uniqueness theorems for quasi-series which are calssical results of Measurement theory.

Denition 2.3.1. A relational system M = hA, Ii consisting of a set A and a binary relation I is called classicatory if and only if I is:

1. Reexive: aIa for any a ∈ A.

2. Symmetric: if aIb then bIa for any a, b ∈ A.

3. Transitive: if aIb and bIc then aIc for any a, b, c ∈ A.

Denition 2.3.2. A structure M = hA, I, ∼i is a quasi-series if and only if: 1. hA, Ii is a classicatory system;

2. ∼ is a binary, transitive relation such that every pair of elements are com-parable, i.e, there aren't a, b ∈ A such that a b and b a (linearity). 3. If a, b ∈ A, then only one of the followig hold: a ∼ b, b ∼ a, aIb.

(36)

Proof. 1. We have already proved that ≡T is an equivalence relation on the

subsets of natuaral numbers.

2. ⊆ is indeed a binary, transitive relation. Moreover we know that hAH, ⊆i is a linear structure.

3. Given two arithmetical degrees Σi,Σj, since hAH, ⊆i is a linear structure it

follows that Σi ⊆ Σj or Σj ⊆ Σi. In case only one of the two holds, we are

done. In case both possibilities hold, we have that Σi = Σj, hence, by Post's

theorem, Σi and Σj have the same Turing degree.

Theorem 2.3.1 (Krantz et al. 1971). Let M = hA, I, ∼i be a quasi-series, where hA/Ii is a nite or denumerable set. Then there exists a denumerable numerical structure isomorphic to hA/I, ∼i (note that in this case ∼ is a relation on equivalce classes).

Proof. Since A/I is denumerable, its elements could be enumerated as a0, . . . , an, . . .

and so on. We construct the isomorphism f by induction on the enumeration. Let f(a0) = 0. Suppose f is dened for an−1 and consider an.

There are three cases:

1. ak ∼ an for k = 1, ..., n − 1. Then f(an) = n.

2. an∼ ak for k = 1, ..., n − 1.Then f(an) = −n.

3. There are i, j ≤ n − 1 such that aj ∼ an ∼ ai and for any 1 ≤ k ≤ n − 1,

either ak ∼ aj or ai ∼ ak (note that here linearity is needed). Let f(an) = 1

2[f (ai) + f (aj)].

We complete this section by proving the uniqueness theorem.

Theorem 2.3.2 (Krantz et al. 1971). Let M = hA, I, ∼i be a quasi-series. Then any two numerical structures hN1, R1i and hN2, R2i isomorphic to hA/I, ∼i are

(37)

Proof. We want to nd a function g : N1 → N2 such that if xR1ythen g(x)R2g(y),

i.e, g is the witness of the fact that the two numerical structure are related by a monotone transformation. Let f1, f2 be two isomorphism between hA/I, ∼i and,

rispectively, hN1, R1i and hN2, R2i. Let g = f2◦ f1−1. It is clear that, dened in

this way, g is a function from N1 to N2. Moreover, if xR1y then f1−1(x) ∼ f −1 1 (y);

hence f2(f1−1(x))R2f2(f1−1(y)).

From these two general theorems it follows that it is possible, given the empir-ical structure dened in Section 2.2, to actually measure, through Computability Theory, the diculty of a problem.

2.4 Remarks

Note that, although the proof is straightforward, we have shown non-trivial facts that give us some interesting insight about Computability Theory. In particular, it is not possible to prove Representation and Uniqueness theorems for non-linear structures as (DT, ≤T). The possibility to restrict ourselves to the structure of

arithmetical degrees is given by Post's theorem, which is a non-trivial result. This shows that the possibility to measure the diculty of a problem, as characterized in Section 2.1, does not follow directly from the features of Computability Theory. Consequently, we can not measure diculty in all its wide range, but only a small portion of it. In other words, we can have a measure up to the ω-Turing jump, since AH corresponds to the rst ω stages of the Turing jump, i.e, we deal with A = {a : ∃n(a ≤ 0n_{)}. This fact gives rise to some interesting epistemological}

issues insofar as we can not measure incomparable degrees. In the rst chapter we claimed that Measurement Theory is an adequate theoretical frame to explain what we mean when we talk about degree structures "measuring diculty". The consequence of this setting is that to make rigorous the idea that in Computability Theory we are measuring diculty, we have no epistemological access to some elements of the structure hDT, ≤Ti. Moreover, it is important to notice that all

our construction is based on Turing reducibility which is the only one that permits us to restrict ourselves to the Arithmetical Hierarchy. In the following section, we will explain why our characterization of the scale for measuring diculty is

(38)

parametric insofar as it is based on Turing equivalence rather than many-one equivalence (see Section 1.2.1).

2.4.1 The structure of many-one degrees

We have shown in the rst chapter some of the main features of many-one degrees. In particular we have seen that the two structure hDT, ≤Ti and hDm, ≤mi are

not isomorphic. We now further analyze the structure of many-one degrees. In particular, we deal with the usual model-theoretic concept of denability. We are interested in showing that the subset of arithmetical m-degrees is not denable in the structure of many-one degrees. From this result, we will argue that our measure of diculty is parametric. Remember that, as stated in the rst chapter, the structure of many-one degrees is a distributive upper-semilattice.

Denition 2.4.1. A set of degrees is an ideal if it is closed downward under the join (least upper bound) operator. A principal ideal determined by the degree a is the set

Dm(≤a) = {b|b ≤ a}

.

Proposition 2.4.1 (Odifreddi 1989). Dm(≤ a) and Dm(≤ b) are isomorphic if

and only if there is an automorphism (an ismorphism from a strucuture to itself) of hDm, ≤mi carrying a into b

Proof. One direction is trivial since an automorphism carrying a into b induces an isomorphism between Dm(≤a) and Dm(≤b). Conversely, given an isomprphism

between Dm(≤ a) and Dm(≤ b) we can exteded it to an automorphism by a

back-and-forth argument as presented in [Odifreddi 1989 pp.573-574] The two following corollaries are very relevant to our discussion:

Corollary 2.4.1. 0m is the only m-degree xed under every automorphism and

hence the only denable m-degree.

Proof. Given a > 0m and b such that there exists an isomorphism between

(39)

b. Consequently, a is not xed under automorphism. Since denability can be characterized as invariance under automorphism we have the thesis.

Corollary 2.4.2. Every denable set of m-degrees dierent from {0m} has the

power of the continuum.

Proof. Give a set S 6= {0m} of m-degrees, of power less than the continuum,

choose a ∈ S − {0m}. Take b /∈ S (note that this is possible since |Dm| = 2ℵ0

while |S| < 2ℵ0). Since there is an automorphism of hD

m, ≤mi carrying a into b,

S is not closed under automorphism and hence can not be denable. This follows from the well-known model-theoretic characterization of denability as invariance under automorphism.

It follows that there are classes of m-degrees that are not denable. In par-ticular, it is not possible to dene arithmetical m-degrees. Indeed, the set A = {a : ∃n(a ≤ 0n_)} _{(note that the jump operator is well dened on m-degrees, see}

Exercise VI.2.1 in [Odifreddi 1989]) is at most denumerable and hence it is not denable in hDm, ≤mi. We can conclude that our possibility to clarify the idea

that in Computability Theory we are measuring the diculty of a problem is for-malism dependent and not as robust as the notion of "computable problem", since our restriction to arithmetical degrees is meaningful only in the structure of Turing degrees.

2.5 Fruitful measurement

It is quite clear that the measurement we have dened is an ordinal scale. The above setting gives us the chance of reecting on the notion of fruitful measure-ment, that will be very important in the next chapter. As we have stressed in the rst chapter, it is not needed, to formally dene a scale, that we have an isomor-phism between the empirical structure and the numerical structure. It is enough to have a homomorphism. However, in the case of ordinal scale, a homomorphism would not tell us any deep or interesting fact about the empirical structure we are trying to measure. Indeed, until we do not prove some separation results for the Arithmetical Hierarchy we can not exclude the possibility that our measure assigns

(40)

the same number to problems that we strongly believe have dierent degrees of diculty. Consequently, it seems that to have fruitful ordinal measurement we need to show that our empirical structure has some specic feature such as the possibility of building a hierarchy of ranks that doesn't collapse. In the case of Computability Theory this fact is ensured by Kleene's theorem which shows that AH doesn't collapse. It is only because of this important result that we can say that through Computability Theory we are actually measuring the diculty of a problem. To further demonstrate this thesis, we can take a look at other ordinal scales, that are well established in scientic practice, showing that the possibility of building a hierarchy that doesn't collapse is a conditio sine qua non of fruitful ordinal measurement. A very important example we will deal with is Mohs' scale. The reasaon is that this scale is very simple and is not based on other scales. Although, as stressed in Chapter One, from a mathematical point of view the dis-tinction between fundamental and derived measurement is nowadays considered irrelevant, this becomes very important in our discussion. Indeed, the importance of separation results is more evident in fundamental ordinal scales (such as Mohs' scale) than in derived ordinal scales (such as Beaufort's scale). This happens be-cause, for example in Beaufort's scale, ranks are separeated trivially by the fact that to each rank are assigned dierent intervals of wind speed. After this impor-tant clarication, we can nally show that in Mohs' scale it is possible to build a hierarchy that doesn't collapse.

2.5.1 Degrees of Hardeness

Mohs' scale is used to measure mineral hardness through the ability of harder material to scratch softer material. Consequently, the empirical structure we are considering consists of a set M (minerals) and a binary relation S on M (to scratch, we will write S(x, y) to say that x scratches y). Given x, y ∈ M we can say that x ≤S y if and only if ¬S(x, y). Moreover, if it happens also that ¬S(y, x) then

we can say that x ≡S y. Consequently, we can dene an ordinal scale in the same

manner we have done for Computability Theory in the previous sections. The crucial point is that we can show, by an experimental proof, that the hierarchy of ranks doesn't collapse. Indeed, we can give an experimental proof that a mineral

(41)

measuring 1 on the Mohs scale (call it x) doesn't scratch a mineral measuring 2 (call it y), i.e, ¬S(x, y). In the same manner, we can also show that S(y, x), hence, by denition, x 6≡S y. We can repeat this reasoning for all the degrees, which are

nite, to show that the hierarchy of degrees of hardness doesn't collapse. Without such a proof it would be still possible, as we have pointed out for Computability Theory, to dene a scale and to prove Representation and Uniqueness theorems via a homomorphism rather than an isomorphism. Nevertheless, such an ordinal scale would be useless. Indeed, we could have the situation in which we would not be able to use the scale to distinguish between dierent degree of hardnesses.

2.6 Main points of the chapter

We have described what specic notion of "diculty" we are interested in. More-over, we have shown that it is possible to say in a mathematically precise way that Computability Theory provides a measure of diculty. Finally, we detected that this approach reveals some interesting fact about both Computability Theory and Measurement Theory. In particular, we derived from our construction some con-sideration about the epistemological status of incomparable degrees. Moreover, we showed that our possibility of formally measuring the diculty of a problem is for-malism dependent and not as robust as other important notions of Computability Theory such as "computable problem". About Measurement Theory, we argued, looking at our construction and using Mohs' scale to further explain the point, that fundamental ordinal scales are fruitful insofar as we can show separation results within their hierarchies of degrees.

(42)

Chapter 3 Measuring degrees of complexity

We will follow the setting of the previous chapter to show what are the critical issues regarding the possibility that Computational Complexity Theory provides a measure for degrees of complexity. It will turn out that, although it is possible to dene a scale as we have done for Computability Theory, this scale doesn't constitute a satisfactory measure of complexity, since the "empirical structure" we deal with lacks a complete characterization.

3.1 On the concept of complexity

As for "dicult", the adjective "complex" is used in a wide spectrum of situations and with very dierent meanings. Our aim is to circumscribe the notion of com-plexity we would like to deal with. It is important to keep in mind that this notion does not come, unlike the concept of "dicult", from a strong philosophical frame as Hilbert's program. Consequently, this notion has been characterized in a hazy way; this fact, as we will see better in the last chapter, led to a characterization of complexity which can be declined in two dierent forms: an absolute form and a relative form. The indicted characterization is the following: given a recursive problem, its complexity is given by the amount of resources we must use to solve it practically. This means, in an absolute sense, that given a particular problem, i.e, an instance, we want to know the amount of resources employed by a particular algorithm to solve it. However, it is widely preferred the relative form: given a

(43)

problem, i.e an innite collection of instances, we want to know how fast the use of resources grows as the input size changes. The reason why the relative version is preferred is that through it we can compare the complexity of problems in a more general way. The merits of this setting are well-known: in particular, it permits to formulate interesting questions in a mathematical rigorous form. From now on we will deal with this particular notion of complexity that leads to the formulation of Computational Complexity theory as presented in the rst chapter. Consequently, we are interested to understand if we can measure degrees of complexity through Computational Complexity Theory. It is worth to emphasize that the notion of problem here described, i.e the notion of decision problem, is not the one usu-ally considered by philosophers and mathematicians. Consider, for example, the following considerations:

We do not dene the notion of a problem but explain it by means of some examples:

1. Find four integers x, y, z and n such that xn+ yn _{= z}n_{, n >}₂

2. Prove that Fermat's theorem is false.

3. Construct a circle passing through three given points (x, y, z). 4. Given one root of the equation ax2 _{+ bx + c = 0, nd the other}

root.

5. Assuming that the number π has a rational expression π = m/n, nd a similar expression for the number e.

The fourth and fth problems are examples of conditional problems; the premise of the latter is false, and hence the fth problem is mean-ingless or empty [...] We believe that these examples and explanations allow us to use unambiguously the notions of problem and solution of a problem in all the cases encountered in specic elds of mathe-matics.