TD d’algorithmique numéro 11 - Olivier Bodini et Natacha Portier

lundi 3 décembre 2001

Question 1 ⋆ Sur le nombre de racines réelles d’un polynôme de ℝ[X] dans un intervalle ⋆

Soit f un polynôme de ℝ[X] et soient a et b deux réels, a < b. On dit qu’un suite de polynômes f_{0} = f, f_{1}, ..., f_{s} est une suite de Sturm pour f sur [a, b] lorsque les conditions suivantes sont vérifiées :

1. f(a) × f(b) ≠ 0,

2. la fonction polynôme f_{s} ne s’annule pas sur [a, b],

3. si c est un réel tel que a < c < b et f_{j}(c) = 0 pour un indice j vérifiant 0 < j < s, alors on a f_{j−1}(c) × f_{j+1}(c) < 0,

4. si c est un réel tel que a < c < b et f(c) = 0, alors le polynôme produit f(c) × f_{1}(c) est du signe de x − c au voisinage du point c.

A une telle suite et à un point x ∈]a, b[, on associe le nombre de variations de signe de la suite au point x, noté V (f_{0} = f, f_{1}, ..., f_{s}; x) (ou plus simplement V (x)), défini par la formule :

V (x) = |{(i, j) ; 0 ≤ i < j ≤ s; f_{i}(x) × f_{j}(x) < 0 et f_{k}(x) = 0 si i < k < j}|

Question 1,1 ⋆ Théorème de Sturm ⋆

Montrer le théorème suivant : Soit f un polynôme à coefficient réels et soient a et b deux réels, a < b. Si f_{0} = f, f_{1}, ..., f_{s} est une suite de Sturm pour f sur [a, b], alors le nombre de racines distintes de f sur l’intervalle [a, b] est égal à V (a) − V (b).

Question 1,2 ⋆ construction d’une suite de Sturm ⋆

Soit f un polynôme à coefficient réels et soient a et b deux réels, a < b. Considérons la suite f_{0} = f, f_{1}, ..., f_{s} définie par : f_{0} = f, f_{1} = f′, f_{2} = −f mod f′, ..., f_{i+1} = −f_{i−1} mod f_{i}, ..., f_{s+1} = 0, alors la suite g_{i} = f_{i}/f_{s}, 0 ≤ i ≤ s, est une suite de Sturm pour g_{0} sur [a, b], pourvu que l’on ait g_{0}(a)×g_{0}(b) ≠ 0.

Question 1,3 ⋆ algorithme ⋆

Montrer le théorème suivant : Soit f un polynôme à coefficient réels et soient a et b deux réels, a < b. Considérons la suite f_{0} = f, f_{1}, ..., f_{s} définie par : f_{0} = f, f_{1} = f′, f_{2} = −f mod f′, ..., f_{i+1} = −f_{i−1} mod f_{i}, ..., f_{s+1} = 0, alors si f(a) et f(b) sont non nuls, le nombre de racines distintes de f sur l’intervalle [a, b] est égal à V (a) − V (b). En déduire un algorithme donnant le nombre de racines réelles de f dans l’intervalle [a, b].

Question 2 ⋆ SAT-n ⋆

On appelle SAT-n le problème SAT restreint aux formules qui n’ont pas plus de n occurences de la même variable.

Question 2,1 ⋆ SAT-3 ⋆

Montrer que SAT-3 n’est pas plus facile que SAT, et donc pas plus facile que SAT-n.

Question 2,2 ⋆ SAT-2 ⋆

Soit x une variable apparaissant dans la formule F de SAT-2. Trouver une formule équivalente à F et dans laquelle la variable x n’apparaisse plus.

En déduire un algorithme polynomial pour SAT-2.

Question 3 ⋆ Variantes de 3-sat ⋆

Montrer la NP complétude des deux variantes de 3-sat suivantes :

1. 3-sat NAE (not all equal), où l’on impose que les trois variables de chaque clause ne soient pas toutes à la même valeur ;

2. 3-sat OIT (one in three), où l’on impose qu’exactement une variable soit à vrai dans chaque clause.

Question 2 ⋆ SAT-n ⋆

On appelle SAT-n le problème SAT restreint aux formules qui n’ont pas plus de n occurences de la même variable.

Question 2,1 ⋆ SAT-3 ⋆

Montrer que SAT-3 n’est pas plus facile que SAT, et donc pas plus facile que SAT-n.

Question 2,2 ⋆ SAT-2 ⋆

Soit x une variable apparaissant dans la formule F de SAT-2. Trouver une formule équivalente à F et dans laquelle la variable x n’apparaisse plus.

En déduire un algorithme polynomial pour SAT-2.

Question 3 ⋆ Variantes de 3-sat ⋆

Montrer la NP complétude des deux variantes de 3-sat suivantes :

1. 3-sat NAE (not all equal), où l’on impose que les trois variables de chaque clause ne soient pas toutes à la même valeur ;

2. 3-sat OIT (one in three), où l’on impose qu’exactement une variable soit à vrai dans chaque clause.