1.4 Etat de l'art
- Gardner et al. [8] ont montré que le problème
de reconstruction d'une matrice binaire est NP-complet pour une dimension du
tableau et un nombre d'axes non parallèles de projection bien
déterminés.
- Woeginger [5] a montré que l'existence,
l'unicité et la reconstruction d'une matrice binaire sont des
problèmes NP-complet et redeviennent polynomial selon le type de convexe
à reconstruire.
- Barcucci et al.[4] ont signalé que l'existence d'une
solution initiale est un problème NP-complet et la reconstruction est un
problème NP-difficile pour de type convexe bien déterminé
et pour d'autre devient un problème polynomial.
- Le problème de reconstruction de matrices binaires
peut être vu comme un problème de reconstruction d'un tableau
monocoloré où toutes les cellules de valeur 1 sont
colorées en noir et toutes les cellules de valeur 0 sont colorées
en blanc. Dans ce contexte, Chrobak et Dflrr [7] ont démontré que
le problème est NP-complet.
- Ryser [6] a signalé que l'existence, l'unicité
et la reconstruction d'une solution sont des problèmes polynomiaux pour
une image de taille réduite. Il a montré aussi que l'existence et
l'unicité deviennent des problèmes NP-complet et la
reconstruction devient un problème NP-difficile concernant l'image de
taille importante.
1.5 Conclusion
On a étudié, dans ce chapitre, le
problème de reconstruction de matrices binaires et on a constaté
que cette reconstruction peut être vue comme un problème de
reconstruction d'un tableau monocoloré où toutes les cellules de
valeur 1 sont colorées en noir et toutes les cellules de valeur 0 sont
colorées en blanc.
Et on a constaté aussi que dans certain cas la
vérification de l'existence et l'unicité est un problème
polynomial et dans d'autre redevient NP-complet selon la taille de la matrice
et le type de convexe à reconstruire.
7
| 
