Computational Complexity and Computability
Lecture 1 – Introduction, Motivation & History
Koushik Pal
University of Toronto
January 11, 2021
Computability Theory & Computable Functions
Question
What is an algorithm?
What is a computable function?
Informally, an algorithm is a sequence of computational steps that converts an input set to an output set.
Informally, a computable function is a function f : A → B such that there is a mechanical procedure for computing the result f(a) ∈ B for every a ∈ A.
Computability Theory is the study of computable functions and the limits of this notion.
Computable Functions – Examples & Non-examples
Example
add:N×N→N:(a,b)→a+b
exp:N→N:n→n
check : String → {, }, where
if p is a syntactically valid Python program check(p) = otherwise.
terminate : String → {, }, where
terminate(p) =
if p is a syntactically valid Python program without any user interaction that terminates
otherwise. #
Computable Functions – Examples & Non-examples
Example
diophantine : {Polynomials in variable} → {, }, where if p has an integer solution
diophantine(p) = otherwise.
diophantinen : {Polynomials in n variables} → {, }, where
if p has an integer solution diophantinen(p) = otherwise. #
Problems in Computability
Precise definition of “computable” – mathematical definition
Show that the definition is “correct” – philosophical argument
Develop methods for showing some functions are computable and some are not – computer science
When can the calculations be done effectively? – Complexity theory
Does a particular problem have a fast solution? – Time Complexity
Does a particular problem have a solution requiring a small amount of memory? – Space Complexity
Can the task of deciding one problem be reduced to deciding another problem? – Reducibility theory
Different areas
Mathematics
Philosophy
Computer Science
By the end of the 19th century, mathematics had become more rigorous and mathematical logic had also been developed.
Complexity theory has its roots in studies in mathematical logic and these earlier questions about maths.
History
Leibnitz (1670) Leibnitz built a first mechanical calculator. He was think- ing about building a machine that could manipulate symbols in order to deter- mine the truth values of mathematical statements. He noticed that a first step would be to introduce a precise formal language, and he was working on defin- ing such a language.
Gauss (1798) Gauss in Disquisitiones Arithmeticae wondered about if there is an efficient algorithm for factoring inte- gers.
History
Hilbert (1900) Hilbert announced a list of 23 problems to the mathematics world, many of which proved to be very influen- tial for 20th-century mathematics. The 10th problem on his list turned out to be fundamental for Computability Theory: Is there an algorithm to decide if a given multivariable polynomial p(x, . . . , xn) has an integer solution?
Hilbert (1928) Hilbert had already de- veloped a theory for formalizing mathe- matical proofs. He posed the Entschei- dungsproblem (decision problem):
Is there an algorithm that decides whether a mathematical formula is a con- sequence of his theory?
History
Godel (1931) Godel in his famous In- completeness Theorem showed that any consistent formal recursive system F within which a certain amount of ele- mentary arithmetic can be carriedout is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.
By the Church-Turing thesis, this im- plies that Entscheidungsproblem is un- solvable.
History
Figure: Stephen Figure: Emil Post Figure: Alonzo Figure: Alan Cole Kleene Church Mathison Turing
Kleene, Post, Church, Turing (1930s) – different models of computability
Church-Turing Thesis (1936) All these models are equivalent in computation power!
History
Church (1936) Church shows the unde- cidability of equality in the λ-calculus.
Turing (1936) Turing shows the unsolv- ability of the halting problem. That prob- lem turns out to be the most important undecidable problem.
Post (1944) studies degrees of unsolv- ability, gives birth to degree theory.
History
Figure: Yuri Matiyasevich
Figure: Hilary Putnam
Figure: Martin Davis
Figure: Julia Robinson
Matiyasevich (1970) Matiyasevich, building on works of Putnam, Davis and Robinson, gave a negative answer to Hilbert’s 10th problem.
History
Cook (1971) Cook introduces P and NP, proves NP-Completeness for SAT, and poses the famous question: is P = NP?
Today
P = NP? is still an open question.
Complexity Theory has become a big research area.
Lots of complexity classes defined for various models of computation
Alternative models of computation are studied, for example, quantum computing, genetic algorithms
Parallel lines of research in mathematical logic, where computability theory is known as recursion theory and computable functions are called recursive functions.
Recap
Language
Regular language
Deterministic Finite automaton (DFA)
Non-deterministic Finite Automata (NFA)
Theorem
A language is regular
⇐⇒ some regular expression describes it ⇐⇒ a DFA recognizes it
⇐⇒ an NFA recognizes it.