Calculabilité et Complexité

07/09/23 - cours 1

site: https://vpenelle.pages.emi.u-bordeaux.fr/coca/

CC: projet + DS/partiel Exam 3h

2 sessions

livre de Papadimitriou: très important pour la complexité

(bd sur les logiciens des années 1920-1930)

“A beautiful mile” (John Nash) (film)

p22

Problème 2: $$ 1 < n < 2^k k bits 2,3,...,\sqrt(n) < 2^{k/2} $$

Problème 3: pattern matching -> linéaire

Problème 4: compilation -> automate à pile

Problème 5: exponentiel (3ⁿ)

p26

DFS: O(|V|+|E|) -> linéaire

Dijkstra: O(|V|(|E|+log(|V|))) -> quadratique

linéaire: n quadratique: n² cubique: n³

11/09/23 - cours 2

A Automate fini L(A) ≠ ∅ ? ⇔ ∃ chemin de I vers F

Si on a 2 automates, L(A₁)⋂L(A₂) ≠ ∅ ? facile

Si on a n automates, L(A₁) ∩ ... ∩ L(A_n) ≠ ∅ ? |A_i| = k |Π_i = 1ⁿA_i| = kⁿ

Logique propositionnelle (p29/134)

-> SAT

CNF: “un ‘et’ de ‘ou’” (ex: $(x_1 \vee\overline{x_2} \vee\overline{x_4}) \wedge(\overline{x_1} \vee x_2 \vee x_3)$

CNF: chaque clause doit avoir 3 litéraux différents.

circuit booléen: formule sous forme d’arbre compressée (on peut réutiliser des sous-formules) description plus succinte (= compressée) de formules booléennes

SAT: Entrée: ϕ (en CNF) Sortie: Oui si ϕ est satisfait

Algo naif: on teste toutes les valuations des x₁, ..., x_n

Tester si σ satisfait ϕ se fait en temps |ϕ|

Tester si ϕ est satisfaisable: temps 2ⁿ|ϕ|

ϕ −  > ϕ̃: - on teste si ϕ est satisfaisable - si oui, alors ϕ̃ = 1 - si non, alors ϕ̃ = 0 ($x_1 \wedge\overline{x_1} \wedge\overline{x_1}$ par exemple) (exemple grossier, en réalité il faut des litéraux différents)

ϕ − >^simpleϕ̃ tq ϕ est satisfaisable ⇔ $\widetilde{phi}$ est satisfaisable

exemple: clause de taille 2

Clause $(x \vee\overline{y}) = Ci$

Nouvelle variable t

$\phi_i = (x \vee\overline{y} \vee t) \wedge(x \vee\overline{y} \vee\overline{t})$

pour x = y = 1: Ci vrai => ϕ_i vrai

pour x = 0, y = 1: ϕ_i ne peut pas être vrai, peu importe la valeur de t.

-> p38

c’est linéaire dans |ϕ| -> polynomial

Cliques

algo naif pour clique: complexité n^k (pas polynomial car on peut avoir k = n et donc nⁿ)

par contre si on fait un algo “Clique 4” qui fixe k=4, alors complexité n⁴ => polynomial

On va voir qu’on peut réduire 3-SAT vers Clique.

=> p43

18/09/23 - cours 3

rappel:

SAT: - Entrée: formule ϕ en CNF (ϕ=ϕ(x₁,...,x_n)) - Question: est-ce qu’il existe val: {x₁, ..., x_n} → {0, 1} tq val satisfait ϕ ?

Problème d’évaluation: - Entrée: formule ϕ, valuation val - Question: est-ce que ϕ est vraie sous val ? - Problème facile: P (temps polynomial)

Réduction clique ≤_p SAT (clique vers SAT)

Idée: X(v,i) doit être vrai si v est le i-ème sommet d’une clique

Contraintes:

1. Parmi les {X(v,i)|v ∈ V}, exactement une est vraie (une liste de k sommets)
2. Parmi les {X(v,j)|1 ≤ j ≤ k}, il y a au plus une qui est vraie (la liste n’a pas de sommets répétés)
3. La liste est bien une clique: les éléments sont reliés 2 à 2.

1. $_1 = $ $\bigwedge_{i=1}^{k} [ \bigvee_{v = 1}^{n} x(v,i) \wedge\bigwedge_{v\neq w; v, w = 1}{n} (\overline{x(v,i)} \vee\overline{x(w,i)}$
2. $_2 = $ $\bigwedge_{v=1}^{n} \bigwedge_{j \neq l;j,l = 1}^{k} (\overline{x(v,j)} \vee\overline{x(v,l)})$
3. $_3 = $ $\bigwedge_{j \neq l; j,l=1}^{k} \bigvee_{(v, w) \in E}^{} (x(v,j) \wedge x(w, l))$

3’ (en CNF): $\bigwedge_{j \neq l; j, l = 1}^{k} \bigwedge_{(v, w) \nin E}^{} (\overline{x(v,j)} \vee\overline{x(w, l)})$

G, K → ϕ₁ ∧ ϕ₂ ∧ ϕ₃

I. G contient une clique de taille K ⇔ ϕ₁ ∧ ϕ₂ ∧ ϕ₃ est satisfaisable II. On peut calculer ϕ₁, phi₂, phi₃ en temps polynomial !

$#$ variables: k ⋅ n taille(ϕ₁)  ∈ 𝒪(k⋅n²) taille(ϕ₂)  ∈ 𝒪(n⋅k²) taille(ϕ₃)  ∈ 𝒪(k²⋅m)

(=>)

Supposons C = {v₁, ..., v_k} est une clique (de taille k)

On prend la valuation val(v_i, i) = vrai, 1 ≤ i ≤ k et val(v_, i) = faux sinon

ϕ₁ est satisfaite par val, car ∀i: val(v_, i) est vrai seulement pour v = v_i

ϕ₂ ” ” ” ” , car ∀l ≠ j: v_e ≠ v_j

ϕ₃ ” ” ” ” , car ∀l ≠ j: (v_e, v_j)  ∈ E

(<==)

Soit val une valuation qui satisfait ϕ₁ ∧ ϕ₂ ∧ ϕ₃

Soit v_i l’unique (ϕ₁ garantit ça) sommet tq val met x(v_i, i) à vrai

{v₁, ..., v_k} est de taille k (ϕ₂ le garandit) et c’est une clique (ϕ₃ le dit)

3-coloration

|ϕ₁| ∈ 𝒪(n)

|ϕ₂| ∈ 𝒪(m)

|ϕ| ∈ 𝒪(n+m)

p48

si sommet “résultat” pas relié à 0: le graphe est toujours 3-coloriable, même si la formule n’est pas SAT.

p49

1. x instance positive de A₁ ⇔ f(x) instance positive de A₂ (f: fonction de réduction)

2. A₁≤_pA₂ via réduction polynomiale f

   A₂≤_pA₃ via ” ” g

   A₁→^fA₂→^gA₃

   A₁→^g ⨾ fA₃

Rq1: g ⨾ f se calcule en P

taille(f(x)) polynomiale en taille(x)

donc le calcul de g(f(x)) se fait en temps poly en taille(x)

ex: f se calcule en 𝒪(n²) g ” ” ” 𝒪(n³)

-> g ⨾ f temps 𝒪(n⁶)

25/09/23 - cours 4

p50/134

Classe NP

• rapels sur SAT
  • évaluer ϕ sous val -> temps 𝒪(|ϕ|)
  • une sol est de taille 𝒪(|ϕ|)

à propos du DS

DS 23/10/23 10h15-12h15 A9 amphis 2,3

Projet: en binome On va faire des réductions

Retour au cours

Chemin Hamiltonien (CH)

Entrée G = (V,E)

Q: Existe-t’il un chemin v₁, v₂, ..., v_n dans G tq V = {v₁, ..., v_n}, |V| = n (tous les sommets apparaissent exactement une fois)

Solution = suite v₁, v₂, ..., v_n, v_i ∈ V

[elle doit être chemin et v_i ≠ v_j, ∀i ≠ j]

Vérificateur pour CH:

prend en entrée G = (V,E), |V| = n et une suite v₁, ..., v_n

Il vérifie que

1. v₁, ..., v_n est chemin de G (𝒪(|G|)

2. v_i ≠ v_j, ∀i ≠ j (𝒪(n))

Si G est instance + de CH alors il existe une solution v₁, ..., v_n qui montre ça.

Classe NP

Classe NP: problèmes qui possèdent des vérificateurs polynomiaux

Classe P: probèlemes qui possèdent des algorithmes polynomiaux

Pourquoi c’est évident que $P \inclus NP$?

P -> algo polynomial M -> M travaille sur <x, y> avec x entrée du problème y = ϵ

algo poly est cas particulier d’un vérificateur poly (y = ϵ)

en gros, pour P, sans donner une solution, on peut résoudre le problème en temps polynomial. Pour NP, avec une solution donnée, on peut résoudre le problème en temps polynomial. Donc si on donne une solution à P, il peut l’ignorer et quand même résoudre le problème en temps polynomial.

autres classes plus compliquées: PSPACE, ExpTime, …

réduction de CH vers SAT

CH≤_pSAT G = (V,E) V = {1, ..., n}

On “code” la solution par x(i,j)

x(i,j) vrai ⇔ le i-ème sommet de la solution est j

1 ≤ i, j ≤ n

1. Chaque sommet apparait dans la suite. $$\bigwedge_{j=1}^{n} \bigvee_{i=1}^{n} x(i, j)$$

2. (Chaque sommet apparait au plus 1 fois.) (pas besoin) $$\bigwedge_{j=1}^{n} \bigwedge_{i \neq i'} (\overline{x(i,j)} \vee\overline{x(i',j)})$$

3. La suite est un chemin. $$\bigwedge_{i=1}^{n-1} \bigvee_{(u,v) \in E} (x(i,u) \wedge x(i+1, v))$$

(2’) $$\bigwedge_{i=1}^{n} \bigwedge_{j \neq k} (\overline{x(i,j)} \vee\overline{x(i, k)})$$

NP-Complet

On verra que SAT est NP-difficile:

-> NP-complet: SAT, 3-col, CH

Si A est NP-Complet et A ∈ P alors P = NP.

A = SAT

Supposons que SAT a un algorithme polynomial M.

On considère B ∈ NP quelconque.

SAT étant NP-difficile $\RightArrow^def$ B≤_pSAT

[x -> f -> f(x) -> M -> oui/non] algorithme pour B polynomial

p56/134: cet algo est poly (n appels à P)

• exemple avec 3-COL (faite au tableau, facile à faire, on dessine le graphe + 3 sommets {1,2,3} reliés entre eux. Et si un sommet du graphe est relié à 2 couleurs, alors il est de la 3ième couleur)

-> réduction de Turing

Résumé de fin de cours

Pour montrer que A ∈ NP:

• quelles sont les solutions ?
• ∀ entrée + il existe une solution de taille poly
• que fait le vérificateur V avec (x,y) et quel est le temps pour vérifier ?

Vu ILP (Programmation Linéaire sur les Entiers)

02/10/23 - cours 5

p58/134 - Théorème de Cook-Levin

p59

NP:

• classe des problèmes qui ont des vérificateurs polynomiaux
• • x instance positive ⇔ il existe y de taille poly(|x|) tq V(x,y) accepte

NP-complet:

• appartient à NP
• NP-difficile: tout pb de NP se réduit à ce prob (≤_p)

Questions pour savoir si A ∈ NP (2.)

1. quels certificats pour A

2. quel vérificateur pour A

• x instance de A
• f(x): formule booléenne
• certificat pour x: valuation des variables de f(x)

2. vérificateur:

• il calcule la formule f(x)
• il vérifie que la valuation satisfait f(x)

-> poly car ≤_p

( projet: partie 2 ici (réduction vers SAT)

partie 1: plus difficile )

p61

Cicruit booléen C = graphe acyclique avec des noeuds internes étiquetés par des ∧, ∨, $\not$, des feuilles étiquetées par z₁, ..., z_n et un noeud sortie.

(^)
^ ^  ^
| |  |
...  |
^ ^  | n
| |  |
(^)  |
^ ^  v
| |
(x)

-> formule de taille 2ⁿ

1. Circuit-Eval

Entrée: Circuit C(z₁,...,z_n) + valuation val:{1, ..., n} → {tt, ff}

Question: Est-ce que C s’évalue à tt sous val ?

Circuit-Eval ∈ P

2. Circuit-SAT

Entrée: Circuit C(z₁,...,z_n)

Question: Existe-t-il val:{1, ..., n} → {tt, ff} qui satisfait C ?

Circuit-SAT ∈ NP:

• certificat = val
• vérificateur V: parcourt C en DFS et évalue C sous val

-> à la fin de la p61, on a fait A ≤_p Circuit-SAT

Circuit-SAT ≤_p SAT

C(z₁,...,z_n) → ϕ(z₁,...,z_n,t₁,...,t_m)

1. |phi| poly dans |C|
2. C satisfaisable ⇔ ϕ satisfaisable

Remarque: applatir C: mauvaise idée (ϕ peut être exponentiel)

Les variables additionnelles (t₁, ..., t_m) sont pour chaque noeud de C:

noeud v de C → variable y_v

1) $v$ feuille, étiquetée par $z_i$
    contrainte $y_v \rightleftarrow z_i$ ($(\not{y_v} \or z_i) \and (y_v \or \not{z_i})$)

2) $v$ = AND($v_1, v_2$)
    contrainte: $y_v \rightleftarrow y_{v_1} \and y_{v_2}$

3) $v$ = OR($v_1, v_2$)
    contrainte: $y_v \rightleftarrow y_{v_1} \or y_{v_2}$

4) $v$ = NOT($v_1$)
    contrainte: $y_v \rightleftarrow \not{y_{v_1}}$

-> ce qu’on a vu en TD -> formule de taille linéaire par rapport au circuit

p61:

1. Observation
2. A ≤_p Circuit-SAT

ce qu’on a écrit ici: Circuit-SAT ≤_p SAT

donc c’est bon, on a montré A ≤_p SAT pour tout A ∈ NP

fin cours -> on voit un exemple

Sujet d’examen Juin18

réduction de Clique vers SAT

certificat: X₁, ..., X_k ⊂ V, k ≤ |E| -> taille poly 𝒪(m,n)

vérificateur (G, X₁, ..., X_k):

• vérifie que chaque X_i est clique 𝒪(k⋅n²)
• et que chaque arête est couverte par un des X_i 𝒪(m⋅k)

1. x_i est une clique

$$\bigwedge_{i=1}^{k} \bigwedge_{u \neq v, u,v=1}^{n} (u, v) \nin E \rightarrow (\overline{x(u,i)} \vee\overline{x(v,i)}$$ -> 𝒪(k ⋅ n²

2. Toute arête est couverte:

$$\bigwedge_{u \neq v, (u,v) \in E} \bigvee_{i=1}^{k} (x(u,i) \wedge x(v,i))$$ -> 𝒪(m ⋅ k

Réduction

• On prouve que 1 et 2 fontionnent

• 1 + 2 => X_i cliques qui couvrent E

09/10/23 - cours 6

p62/134

Problèmes de type “sac à dos”: problème d’optimisation

On commence avec un problème de taille (Somme d’entiers)

Somme de 2 nb binaires à m bits: 𝒪(m); Multiplication de 2 nb binaires à m bits: 𝒪(m²)

Problème “Partition”: celui qu’on aura dans le projet

Remarque:

• Nb binaires à k bits -> valeurs 0 ≤ v ≤ 2^k

• Nb codés en unaire de longueur k: -> valeurs 0 ≤ v ≤ k

Somme d'entiers - unaire
    indices 1..p // poly
    somme s // poly
    Pour tout 1 <= r <= p, pour tout s' <= s
        existe-t-il des 1 <= i_1, ..., i_t <= r tq
            (Somme pour j de 1 à t de x[i][j]) = s'

p64: Somme d’entiers ≤_p Partition

x₁, ..., x_p, s → y₁, ..., y_r

X → x₁, ..., x_p, X − 2s

On part d’un ensemble X = {x₁, ..., x_p}. Si Somme d’entiers est bon, alors la somme d’une partie de ces x est égale à s.

On prend ces entiers et X − 2s d’un côté, la somme de tout ça donne s + (X−2s) = X − s.

De l’autre côté, on prend tous les autres x. Donc X − s.

Ainsi, si on a une somme égale à s, on a la partition, sinon c’est impossible de partitionner.

3-SAT ≤_p Somme d’entiers

Dans toute sol de Somme

1. ∀1 ≤ i ≤ n: soit y_i ou z_i est dans la sol (pas les 2)

2. ∀1 ≤ j ≤ m: parmi les entiers y_i, z_i qui sont dans la sol, au moins un a 1 à la position j.

exemple: $(x_1 \vee\overline{x_3}) \wedge(\overline{x_1} \vee x_2 \vee x_3)$

m = 2 (il y a 2 clauses)

(nombres codés en base 10)

on ajoute t₁ = w₁ = 10 et t₂ = w₂ = 1

s = 1...1|3...3 (j’ajoute les | pour montrer la séparation, mais en réalité c’est un seul nombre)

ici formule sat: x₁ = x₂ = x₃ = tt

 → y₁ + y₂ + y₃ = 111|12

 → 11112 + t₁ + w₁ + t₂ = 111|33

et c’est égal à s.

si x₃ = x₂ = tt et x₁ = ff

 → z₁ + y₂ + y₃ = 111|03

$\RightArrow$ on peut pas transformer le 0 en 3 car on a juste 2 entiers supplémentaires par clause.

. (1) → valuation des vars x_i

• si $y_i \in \text{Sol} \RightArrow \sigma(x_i) = \text{tt}$
• si $z_i \in \text{Sol} \RightArrow \sigma(x_i) = \text{ff}$

σ satisfait ϕ à cause de (2)

→ ∀ clause, il y a au moins un 1 → au moins un littéral de la clause est vrai.

Fin cours; on voit le partiel 2020/2021 (sur EDNA)

16/10/23 - cours 7

A propos du DS

Que sur la partie complexité

aujourd’hui on va voir la partie Calculabilité qui n’y est pas.

DS:

• NP et réductions
• droit à une feuille manuscrite recto verso

Cours

p68/134

f : ℕ → ℕ calculable: il existe un algo qui calcule f → étant donné n ∈ ℕ, on veut f(n)

Question: est-ce qu’il existe des fonctions non-calculables ?

La réponse sera oui, et on va montrer ça en comptant.

Aujourd’hui: quels objets peut-on compter ?

p72: bijections

1. ℕ: logique
2. ℤ: 0, 1, -1, 2, -2, …
3. ℕ²: | | 0 | 1 | 2 | 3 | |:-:|:—–:|:—–:|:—–:|:—–:| | 0 | (0,0) | (0,1) | (0,2) | | | 1 | (1,0) | (1,1) | | | | 2 | (2,0) | | | | | 3 | | | | |

-> on fait les diagonales

4. ℚ -> p/q -> q ∈ ℕ, p ∈ ℤ -> énumérer ℤ * ℕ

5. matrices avec entrées entières

taille de matrice m * n

M = max(a_ij(1 ≤ i ≤ m, 1 ≤ j ≤ n

énumérer ℕ³

-> pour chaque (m,n,M) on énumère toutes les matrices m * n avec valeur absolue  ≤ M

par exemple avec (2,1,2):

(0,0), (0,1), (0,2), (0,−1), (0,−2), (1,0), ...

Diagonalisation de Cantor

Supposons qu’on peut énumérer E : e¹, e², ...

• e¹ : 00000000…
• e² : 0101010101…
• e³ : 000111000111…

on construit e qui suit la diagonale et inverse le bit associé

e₁¹ = 0 → e₁ = 1, …

e = 100…

e n’apparait pas dans le tableau puisque pour chaque eⁱ, e_iⁱ ≠ e_i.

Contradiction => E ne peut pas être énuméré.

p76: LOOP

$x \dotdiv y = \{ \frac{x-y \text{si} x \geq y}{0 \text{sinon}}$

Exercice: x - y

z := x
LOOP(y) DO x := x-1 OD

Exercice: IF (x=0) THEN P ELSE Q FI

y := 1 - x // 1 si x=0; 0 si x > 0
z := 1 - y // 1 si x > 0; 0 si x=0

LOOP(y) DO P OD
LOOP(z) DO Q OD

Exercice: que calcule ce programme ?

LOOP(y) DO x := x-1 OD
z := y
LOOP(x) DO z := z+1 OD

-> calcule le maximum de x et y

Exercice: n mod k

x0 := 0
x1 := 1
...
x(k-1) := (k-1)

LOOP(n) DO
    x := x0 // variable temporaire pour sauver x0
    x0 := x1
    x1 := x2
    ...
    x(k-2) := x(k-1)
    x(k-1) := x
OD
res := x0

Exercice: n div k

x0 = x1 = ... = x(k-1) = 0
LOOP(n) DO
    x = x(k-1) // variable temporaire encore
    x(k-1) := x(k-2)
    ...
    x1 := x0 + 1
    x0 := x
OD
res := x0

k = 2, n = 5

-> 5/2 = 2

-> p78

06/11/23 - cours 8

p78: WHILE

on peut faire une liste: (n₁,n₂,...,n_k) en la codant avec un entier: M = n₁ + n₂ ⋅ N + n₃ ⋅ N² + ... + n_k ⋅ N^k − 1

=> n₁ = M mod N

décoder: division, modulo

p79: GOTO

WHILE-calculable => GOTO-calculable

WHILE (x!=0) DO P OD

P WHILE-calculable, on suppose qu’on a un programme GOTO P’, équivalent à P.

     1  IF (x=0) THEN GOTO 4
     2  P'
     3  GOTO 1
     4  HALT

GOTO-calculable => WHILE-calculable

On utilise une variable de plus: PC (program counter)

notre programme GOTO: P: I₁; I₂; ...; I_k (I_k = HALT)

WHILE (PC != HALT) DO
    IF PC=1 THEN ^Î_1 FI;
    IF PC=2 THEN ^Î_2 FI;
    ...
    IF PC=k-1 THEN ^Î_{k-1} FI;
OD

I peut être:

• x := y +- c
• x := c
• IF (x=0) THEN GOTO l
• GOTO l

Si I = (x := y +- c ou x := c)

alors ^I = (`I; PC := PC + 1`)

Si I = GOTO l

alors ^I = (`PC := l`)

Si I = (IF(x!=0) THEN GOTO l)

alors ^I = (`PC := PC + 1; LOOP(x) DO PC := l OD`)

Si I = (IF(x=0) THEN GOTO l)

alors ^I = (`IF (x=0) THEN PC:=l ELSE PC := PC + 1 FI`)

p81: fonction d’Ackermann

A(1,2):

(1,2)       (1,1)       (1,0)  (0,1)
  |           |           |      |
(0, (1,1))  (0, (1,0))  (0,1)    2

A(0,1) = 2 A(1,0) = 2 $$A(1,1) = A(0, 2$ = 3$ $$A(1,2) = A(0,3) = 4$$

=> Variante

p82:

• B₀(x) = x + 1
• B₁(x) = 2x
• B₂(x) ≥ 2^x ( = 2^x * x (j’avais noté  + x mais à vérifier))

Chaque fonction B_m (pour m fixé) est LOOP-calculable

preuve:

1. B₀(x) = x + 1 => ok
2. Supposons que B_m est LOOP-calculable. On veut montrer que B_m + 1 l’est aussi.

Si P_m est un programme LOOP qui calcule B_m, alors:

P_m + 1 =

LOOP(x) DO
    P_m;
    x_0 := res                 // x_0 = x
    x_1 = x_2 = ... = x_k = 0
OD

=> ok

p83

(oublié sur le diapo: c’est si x est suffisamment grand)

1. preuve que B n’est pas LOOP-calculable (alors que B_m l’est)

Est-il possible qu’il existe M > 0 tq B(m,x) < B_M(max(m,x))

Prenons m = M + 1 = x : B_M + 1(M+1) < B_M(M+1) => faux! (contradiction)

2. exemples de foncitons LOOP-calculables qui satisfont le truc

f(x) = x + 1: m=1

g(x) = x²: m=2

Soit n(P) la … profondeur d’imbrication des boucles LOOP

• n(P) = 0

P utilise que x := y+-c, x := c

-> fct calculées sont f(x) = x +  − c ou f(x) = c

f(x) < B₁(x) (si x suffisamment grand)

• n(P) = 1 (fonction linéaire)

possibilités: LOOP(x) DO x:=x+1 OD ou LOOP(x) DO x:=2 OD

p84: pour tout n(P) = k

• x fois P

S = LOOP(x) DO P OD

n(P) ≤ k

∃m tq les variables de (x fois P):

1 -  ≤ M→^P ≤ B_m(M)

2 -  ≤ B_m(M)→^PB_m ⋅ B_m(M)

…

Après x fois P: les variables de P sont  ≤ B_m ⋅ B_m ⋅ ... ⋅ B_m(x) (x B_m)

S = P₁, P₂, ..., P_r

Si pour chaque P_i:

var de P_i(≤M)→^P_i var de P_i(≤B_m + 1(M))

Après S les var sont  ≤ B_m + 1 ⋅ ... ⋅ B_m + 1(M) (r B_m + 1) leqB_m + 2(M)

Si M > r

remarque

algos “union find”

On peut montrer qu’un algo de “union find” est majoré par l’inverse de la fonction d’Ackermann (donc le logarithme)

On a vu que B₄(2) >  = 2²⁰⁴⁸ ce qui est immense

donc on peut dire que cet algo est majoré par 4

p86: Machines de Turing

p89:

----------------------------------------
... | [] | 0 | 1 | 1 | 1 | [] | [] | ...
           ^
----------------------------------------

entrée: 0111

Ce que ça fait: ça remplace son entrée par des blancs (donc ça l’efface)

Asymétrie: Un calcul peut retourner OUI, NON, ou ne pas s’arrêter.

Fin cours