Introduction
CSC363: Computational Complexity and Computability
Mohammad Mahmoud
This lecture is co-hosted by one of the TAs: Paul Zhang
• Mohammad Mahmoud
PhD, 2019
Cairo University
BSc, 2010 MSc, 2014
Post-doc
Master’s of Statistics
About the Course
Course Outline
• You can find it at the Office of the Registrar Timetable page https://student.utm.utoronto.ca/timetable/
• It includes all information regarding Office hours, grading, and deadlines
• Also includes a course description, learning outcomes, and a list of references
Assessments
• 5 easy short quizzes (3% each): The first will be on Friday the 22nd • 5 assignments (10% each): The first will be on Friday 29th
• No midterm
• No programming
• Final exam (35%). You need to score at least 40% on the exam itself.
Computability
When we were kids
• Learned how to count: 1,2,3 …
• Then, how to add + : through counting (oo + ooo = ooooo) • Later, how to multiply x: repeated addition
It was computation (calculation)
Main characteristics:
• There is a procedure
• There is some initial primitive operation/function (e.g. successor)
Now we are older
• Our procedures are now algorithms
• We build algorithms using some primitive functions • We compute functions using algorithms
Strong Intuition
• Most of the time we are comfortable with our intuitive understanding of what an algorithm is and what computable is.
• Informally, an algorithm is a finite sequence of implementable instructions.
• A function is computable if there is an algorithm to compute it.
Do we need formality?
• That moment when mathematicians realized that they were trying to find an algorithm to solve a problem which is unsolvable by an algorithm.
Hilbert’s 10th Problem (H10)
• In 1900, David Hilbert published 23 problems. The 10th was:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
H10 in modern terms
• Find an algorithm which, for any given Diophantine equation, it can decide whether the equation has a solution with all unknowns taking integer values.
• Note that the algorithm here is meant to be general. In other words, it is the same for any given Diophantine equation.
• Also note that it does not even ask for finding a solution. Just decide if exists or not.
70 years after Hilbert’s request
• The 23 year old Yuri Matiyasevich proved that THERE IS NO such algorithm
Remarks
• Yuri just added the final touch to a work built by many others (Martin Davis, Hilary Putnam, and Julia Robinson).
• The feeling that the problem is unsolvable had been around since 1944
• That feeling was declared by Emil Leon Post
• H10 is not the first problem of that kind, but it is one we can introduce at the moment without much background
The need for formality
• Proving unsolvability by an algorithm requires a solid formulation of which processes we can accept as algorithms
• We should be able to create a list of all algorithms {𝑃 : 𝑒 ∈ 𝑁} 𝑒
(algorithms can be thought of as strings, the set of strings is countable)
• Then show that: for all e, 𝑃 does not solve the given problem. 𝑒
Formal Approaches
• One approach is formalizing the definition of computable function directly (Kurt Gödel)
• Another approach is “mechanical”: an algorithm is a computer program (Alan Turing, Emil Leon Post)
• A computer here is an abstraction of how “any” computer works
• There are several such abstract computer models. We will discuss the Turing Machine in this course.
More about H10
I will not be asking you details about this topic. The goal is the big picture and to introduce some knowledge which should ring a bell later in this course. Also to make you look things up and read around the topic.
That being said, many proofs will be omitted.
Some of the content will be hard at first, and that’s ok. You will take your time later to digest it. It will grow your muscles.
Diophantine Equations
• Diophantine refers to the mathematician Diophantus of Alexandria (3rd century)
• A Diophantine equation is a polynomial equation in more than one unknown in which all the coefficients are integers (in Z).
Recall: Z = {…,-3,-2,-1,0,1,2,3,….}
• We only care about integer solutions
Diophantine Equations: Examples
• 3𝑥2 − 2𝑥𝑦 − 𝑦2𝑧 − 7 = 0 has the following integer solution x =1, y=2, z=-2.
Indeed,3(1)2−2 1 2 − 2 2 −2 −7=3−4+8−7=0 • 𝑥2 + 𝑦2 + 1 = 0 has no integer solutions
Careful, this isn’t the circle equation
Diophantine Equation: General Form
•𝑝𝑎1,…,𝑎𝑘,𝑥1,…,𝑥𝑙 =0
where 𝑝 … stands for a polynomial function, the 𝑥𝑖’s can be the unknowns and the 𝑎𝑖’s can be some (or all) of the coefficients (parameters of particular interest).
Example:3𝑥2−2𝑥𝑦−𝑦2𝑧−7=0canbe𝑝 3,−2,−1,𝑥,𝑦,𝑧 =0 where𝑝 𝑎1,𝑎2,𝑎3,𝑥,𝑦,𝑧 =𝑎1𝑥2 +𝑎2𝑥𝑦+𝑎3𝑦2𝑧−7
• Orcanbe𝑞 7,𝑥,𝑦,𝑧 =0 where
𝑞𝑎,𝑥,𝑦,𝑧 =3𝑥2−2𝑥𝑦−𝑦2𝑧−𝑎
• It can take many forms
Diophantine Sets
• A Diophantine set is a subset 𝑆 of 𝑁𝑘(tuples of natural numbers) for whichthereexistsaDiophantineequation𝑝𝑥ҧ,𝑦ത =0suchthat
𝑆={𝑎ത:(∃𝑚ഥ∈𝑁𝑙)(𝑝𝑎ത,𝑚ഥ =0)}
• Here 𝑥ҧ is a tuple of unknowns of length 𝑘, and 𝑦ത is a tuple of
unknowns of length 𝑙. Also, N = {0,1,2,…}.
• We say 𝑆 is definable by the formula φ 𝑥ҧ = (∃𝑚ഥ)(𝑝 𝑥ҧ,𝑚ഥ = 0) in N.
Diophantine Set: Example
• Consider the set
𝑆={𝑎∈𝑁:(∃𝑚 ,𝑚 ∈𝑁)(𝑚 𝑚 +2𝑚 +2𝑚 +4−𝑎=0)}
Here
𝑝𝑎,𝑥,𝑦 =𝑥𝑦+2𝑦+2𝑥+4−𝑎= 𝑥+2 𝑦+2 −𝑎 •𝑝 𝑎,𝑥,𝑦 =0iff𝑎=(𝑥+2)(𝑦+2)
• S is exactly the set of numbers >2 which are not prime.
121221
• The set S is basically the set of parameter tuples 𝑎ത for which the Diophantineequation𝑝𝑎ത,𝑦ത =0hasasolutioninthenatural numbers
• Recall that when we stated H10, we were talking about integer solutions (not natural)
• In fact, in the statement of H10, if we restrict the problem to finding natural solutions, then the version we get is still equivalent.
H10 (practical version)
• Find an algorithm which, for any given Diophantine equation, it can decide whether the equation has a solution with all unknowns taking natural values.
• Both versions are equivalent in the sense that, if you find an algorithm for one of them, then you can find an algorithm for the other.
• Proving the equivalence is omitted but not hard. It uses a handy fact called Lagrange’s four-square theorem
Lagrange’s four-square theorem
• Every natural number is the sum of the squares of four integers • Example: 31 = 52 + 22 + 12 + 12
Time to Recollect
Short break
H10 and Diophantine sets
• There is the following connection between Diophantine sets and Hilbert’s problem which is:
The existence of an algorithm as mentioned in H10
implies
We can ‘uniformly’ decide membership for any Diophantine set
Decidability
• We mean by that, there is an algorithm which when given any Diophantine set 𝑆 (subset of 𝑁𝑘 say), and any 𝑎ത ∈ 𝑁𝑘 , it can determine if 𝑎ത belongs to S or not.
• In general, a set is decidable if there is an algorithm that can decide its membership, e.g., the set of prime numbers.
What Yuri did
• Yuri filled the last piece of proving that (known as MRDP theorem): A set is Diophantine iff it is listable
• Listable means there is an algorithm (program) that lists its elements. In other words, pops its elements one after the other.
• Listable is also known as computably enumerable (c.e.)
Listable vs Decidable
• Every decidable set is listable (easy to prove)
• The converse is not true (easy once we formally settle the definition
of an algorithm or that of a computable function)
• In other words, there exists a set H which is listable but not decidable
Let’s trace things back
• H is listable but not decidable
• By MRDP, H is Diophantine but not decidable
• The existence of a Diophantine set which is not decidable implies that H10 isn’t solvable (Contra-positive).
• There is the following connection between Diophantine sets and Hilbert’s problem which is:
The existence of an algorithm as mentioned in H10
implies
We can ‘uniformly’ decide membership for any Diophantine set
Done with the H10 story
Take this
• Formal Computability is either Gödel computability, or Turing computability. Both can be proved equivalent.
• Turing computability is mechanical: An algorithm is a Turing Machine (TM)
• AsetislistableifitcanbelistedbyaTM
• A set is decidable if a TM can decide its membership (compute its characteristic/indicator function)
• Every decidable set is listable but not the other way (intuitively kinda obvious, but the proof is through formal computability)
• This implies that H10 is unsolvable (by MRDP which particularly relies on Gödel computability)
Gödel Computability
Recall again when we were little kids
• Counting: successor operation
• Then addition: repeating the successor
• Multiplication: repeating addition
• That repetition process can be generally seen as recursion
Mimicking baby math
• Gödel decided to mimic early calculation
• Defined some basic initial functions
• Then used some fundamental primitive rules to build with them
Initial Functions
1. Thezerofunction:𝟎 𝑛 =0foreveryninN
2. Thesuccessorfunction:𝑠 𝑛 =𝑛+1foreveryninN
3. The projection functions: 𝑈𝑘 𝑖
The k indicates that its input is a tuple of length k, and i means it outputs the i-th component. More precisely,
𝑈 𝑘 𝑚ഥ = 𝑚 𝑖 𝑖
Reinforcing Intuition
• Note that those initial functions are directly computable by instinct • The zero function is like erasing, nothingness
• The successor is what takes us from nothing to something
• The projection is literally choice, ability to distinguish
What could be simpler?!
Beautiful!
Primitive Recursive Functions (PRIM)
• Now it is time to build more complex functions
• We think like induction
• Initial Functions are the base
• Assume we have a bunch of functions that have been built
• We describe how to use the latter to build the next ones (one step more complex)