Algorithm and Complexity 2, année 2024

Complexity: analysis the cost of computation

One of the key driven subject to introduce model of computations is to evaluate the cost of a given computation. The notion of cost should be understood in a very broad way. Depending of the situation, the cost can refer to the time needed to perform a computation, to its memory footprint, to the amount of communication among computers, to the amount of humain/computers interactions required to complete the task, etc.

Complexity Theory is the study of some cost in computational models. Classically it focuses on Turing machine or RAM model with respect to their time and memory usage.

Contrary to what happens with computability, the fact that a model can simulate another model is not very helpful since the simulation can drastically change the cost of the computation.

Time and Space complexity for languages

Given a Turing Machine \(M\), we say that it has a worst-case time complexity \(f\colon\mathbb{N}\to\mathbb{N}\) if for any word \(u\), the length of the execution of \(M\) over \(u\) is less than \(f(|u|)\).

Given a Turing-computable language \(L\) and a function \(f\colon\mathbb{N}\to\mathbb{N}\), we say that \(L\) has a worst-case time complexity \(f\) if there exists a Turing machine \(M\) computing \(L\) with worst-time complexity \(f\).

Several remarks:

• The worst-case time complexity of a language is an intrinsic property of the language.
• Given a Turing Machine, computing its worst-case time complexity is not easy.
• If we find a Turing machine computing \(L\) with some complexity, then we are certain that \(L\) has this worst-case time complexity, but it might be possible that another Turing Machine computing \(L\) provides better complexity. Finding the complexity of a language is much harder than establishing the complexity of one machine.

We often ignore multiplicative constants and focus on asymptotic analysis in complexity Theory. Hence, complexity is usually given using Landau notation. We assume those notations to be well understood already.

Examples

• Quickly prove that the machine computing \(\{a^nb^n \mid n\in\mathbb{N}\}\) has a worst-case time complexity of \(n^2\).
• Prove that \(\{a^nb^n\mid n \in \mathbb{N}\}\) has a worst-cast time complexity \(\geq n\).

Exercice

Let \(L\) be the language of words \(\overline{b_1}^2\#\overline{b_2}^2\#\cdots\#\overline{b_n}^2\) for all \(n\in\mathbb{N}\) such that for all \(i\leq n\) we have \(b_i\in\{0, 2^n\}\) and \(b_i=b_{n-i}\).

What is the complexity of \(L\) with one-Tape Turing Machines and many Tapes Turing Machines.

Time Complexity

DTIME

Given a function \(f\colon\mathbb{N}\to\mathbb{N}\), we denote \(\textrm{DTIME}(f)\) the class of languages with worst-time complexity \(O(f)\).

Observe that if \(f\) is dominated as a function by \(g\) then \(\textrm{DTIME}(f)\subseteq \textrm{DTIME}(g)\).

Those classes are sensible to the model of computation.

Example

\(\{a^n b^n\mid n\in \mathbb{N}\}\) is in \(\textrm{DTIME}(n\mapsto n^2)\) but also in \(\textrm{DTIME}(n\mapsto n^3)\).

In the model of Turing Machine with two tapes, \(\{a^nb^n\mid n\in\mathbb{N}\}\) is in \(\textrm{DTIME}(n\mapsto n)\).

Notations

We will use from now on the notation \(\textrm{DTIME}(f(n))\) instead of \(\textrm{DTIME}(n\mapsto f(n))\)

P

We denote by \(P\) the class of languages computable by Turing machine in polynomial time. Formally, \(\textrm{P}=\bigcup_{d}\textrm{DTIME}(n^d)\). We extend \(\textrm{P}\) to problem with output. Hence, Turing machine with an output tape computing functions.

It is a robust class of complexity: it is (more or less) independent of the model of computation! Hence, we can prove a language is in \(P\) by providing a Python function computing it (using only standard operations).

It is the class of reasonable problems although all problems in \(P\) are not reasonable in practice.

Exercises

• Integer addition in base \(b\geq 1\) is in \(\textrm{P}\)
• Integer multiplication in base \(b\geq 1\) is in \(\textrm{P}\)
• Matrix multiplication in base \(b\geq 1\) is in \(\textrm{P}\)

Questions

• Is Primes factorization in \(P\)?
• Finding integers roots of an integer Polynomial.

EXP

We denote by \(\textrm{Exp}\) the class of languages computable by Turing Machine in exponential time. Formally \(\textrm{Exp}=\bigcup_{d} \textrm{DTIME}(2^{n^d})\). As for \(\textrm{P}\), we extend \(\textrm{Exp}\) to functional problem by considering Turing Machine with an output tape.

Question

• What is the complexity of given one number \(a\) in base \(2\) to compute \(2^a\)?
• What is the complexity of given one number \(a\) in unary to compute \(2^a\)?

The hierarchy Theorem

Their exists a language which is in \(\textrm{Exp}\) but not in \(\textrm{P}\).

Proof

We prove that their exists a language in \(\textrm{DTIME}(2^{n^2})\) but not in \(\textrm{DTIME}(2^n)\). Since \(P\subseteq \textrm{DTIME}(2^n)\), it concludes the proof.

We denote by \(\textrm{TM-encode}\) the function that encode any Turing-Machine over a binary alphabet and \(\textrm{TM-decode}\) the converse function (that take an encoding of Turing Machine and provides a description of the TM.

Then we define the language \(L\) that accept pairs \((u, v)\) such that their exists a Turing Machine \(N\) with \(u=\textrm{TM-encode}(N)\) and execute \(N\) over \((u, v)\) and letting \(n=|u|+|v|\) :

• reject if \(N\) is not over in \(2^n\) steps
• accept iff \(N\) reject otherwise.

Observes that the simulation of \(2^n\) steps of a given Turing machine is doable by a Turing machine in \(n^k2^{n}\) steps, for some \(k\), which show that \(U\) is indeed in \(\textrm{Exp}\). We need to perform the simulation and for each step increase a counter of steps. Each simulation and counter update can be perform in \(n^{O(1)}\) steps, which conclude.

Their exists \(n\) large enough such that \(n^k 2^n < 2^{n^2}\).

Assume by contradiction that \(L\) is doable by a Turing machine \(M\) in \(2^n\) steps. Let \(u=\textrm{TM-encode}(M)\) and \(v\) such that \(|v|+|\textrm{TM-encode}(M)=n\). Then we have:

If \(M\) accepts \((u, v)\), then it means \((u, v)\) is in \(L\), which means that \(M\) reject \((u, v)\) in less than \(2^n\) steps which means \((u, v)\) is not in \(L\).

If \(M\) rejects \((u, v)\) then it means \(M\) accept \((u, v)\) in less than \(2^n\) steps which mean \((u, v)\) is in \(L\).

Hence, we reach a contradiction.

Compiled the: mar. 21 janv. 2025 22:04:09 CET