AI and ML are everywhere. Every problem could possibly be solved by AI! We may want to find the algorithms that solve a problem in a better way, i.e. efficiently and with good accuracy. If we know that a task is intrinsically hard, we could direct towards methodologies which are made for that, avoid spending our time on stupid solutions, inform the stakeholders...
Suppose we wanted to write a python program multiplying two integers, without using the python multiplication operator: our numbers will be considered as lists of digits, having length n, each element of which is a char between 0 and 9. There's multiple methods for solving this.
Provides a precise definition of the computable and many results about it. Born in the 20th century, it has evolved into a fully fledged scientific field. The theoretical notion of computation existed before (and keeps influencing) modern electronic computers.
Computability theory: Computability = is a certain task computable (i.e. solvable by a computer)?
Computational complexity theory: Efficiency = is a certain task solvable in a reasonable amount of time and space (i.e. working memory)? If not, the task may be theoretically computable but pratically uncomputable because of the time or space it requires. This will be the subject of this course.
Computational task: A problem that needs to be solved.
Computational process: A sequence of actions capable of solving a computational task. In the Theory of Computation is taken to be an algorithm (a finite description of a series of elementary computation steps, where the way the next step is determined must be deterministic).
A computational task can have 0..N solving processes. A task with no solving processes is an unsolved task. Distinct processes can solve the same task in different ways and some of them can be unacceptable (i.e. requiring too much time or space).
For example, two 
-digits numbers 
and 
can be multiplied (
) in (at least) two ways.
The first method ("repeated addition") by summing times (
), which for each sum requires steps, hence the total cost is proportional to 
steps.
The second method ("grid method") is the classic method we learnt at elementary school and has a cost proportional to 
steps.
Notice that can be exponential in (
).
The repeated addition is potentially way slower than the grid method because there is a huge (exponential) difference between and 
.
For example, supposing 
and 
(the worst case scenario) and that each step requires a millisecond, the grid method would require a second while the repeated addition 10^80 years.
Computational processes can be classified as P (Polynomial time, efficient), NP (Nondeterministic Polynomial time), NP-complete, NP-hard, EXP (pratically uncomputable).
Proving tasks not solvable by processes beyond a certain level of efficiency is very rarely possible. We can, however, interrelate different tasks to compare their complexity.
Mathematical concepts needed for the course:
- Sets (i.e.
)
- cardinality (i.e.
) - finiteness
- cardinality (i.e.
- Naturals and integers
- Conditions holding for a sufficiently large variable (i.e.
, 
holds if 
such that holds 
) - Floor (i.e.
) - Ceil (i.e.
) -
- We will use 2 as canonical base for logarithms (i.e.
) - String
over the alphabet 
with length 
- Empty string (
) - Set of all string over (
) - Concatenation
of 
and 
- Concatenation
of with itself 
times - Length
of a string
- Empty string (
