Modèles de calcul, TD numéro 6

Natacha Portier lundi 18 avril 2002

Question 1 : un problème P -complet

Considérons un ensemble fini X muni d’une relation ternaire R ⊆ X × X × X et de deux sous-ensembles X_{s} ⊆ X et X_{t} ⊆ X. On définit l’ensemble A comme l’ensemble des sommets accessibles à partir de la source. C’est le plus petit sous-ensemble de X contenant X_{s} et tel que si (x, y, z) ∈ R et y et z sont dans A alors x appartient également à A. Le problème SP S (Solvable Path Systems) est l’ensemble des (X, R, X_{s}, X_{t}) tels que A ∩ X_{t} ≠ ∅.

Question 1,1

Montrer que ce problème est P.

Question 1,2

Une machine de Turing oscillante est une machine de Turing à une demi-bande pour laquelle quel que soit le calcul la tête de lecture explore les cases exactement dans l’ordre suivant : 0 1 0 1 2 1 0 1 2 3 2 1 0 1 2 3 4 3 2 1 0 ... Montrer que tout problème P est décidable en temps polynomial par une machine de Turing oscillante.

Question 1,3

Montrer que les fonctions suivantes sont calculables en espace logarithmique :

• case(t) est le numéro de la case lue à l’instant t (avec case(0) = 0).

• tprec(t) est le dernier moment avant t où la tête de lecture était sur la case case(t). Si t est le premier pas de calcul où la case case(t) est explorée alors par convention tprec(t) = −1.

• vinitiale(t) est la valeur initiale de case(t) à l’instant 0.

Question 1,4 Montrer que SP S est P -complet. Question 2 : programmation linéaire Soit A une matrice n × m à coefficients entiers, B un vecteur ligne de dimension n à coefficients entiers, C un vecteur colonne de dimension m à coefficients entiers et k un entier. Le problème RLP de la programmation linéaire rationnelle est l’ensemble des (A, B, C, k) tels qu’il existe un vecteur ligne X à coefficients rationnels positifs ou nuls satisfaisant AX ≤ B et CX ≥ 0. Si on se restreint aux vecteurs X à coordonnées entières on obtient la programmation linéaire entière ILP. On admet que RLP est P et que ILP est NP. Question 2,1 Montrer que ILP est NP − complet. Question 2,2 Montrer que RLP est P − complet.