GREYC

GREYC

Complexité.

Il existe encore de nombreux problèmes liés aux réseaux dont la complexité est mal connue.

La recherche d'un point du réseau, le plus proche d'un point fixé de l'espace ambiant, (connu sous le nom de CLOSEST POINT) a été prouvée NP-complet par VAN EMDE BOAS en 1981. Mais pour ce qui est de la recherche d'un vecteur le plus court (pour la norme euclidienne) du réseau (connu sous le nom de SHORTEST VECTOR), la preuve de VAN EMDE BOAS ne s'applique plus. Aucun élément de réponse sur la NP-complétude de SHORTEST VECTOR n'existait jusqu'en 1997, avec les récents travaux d'AJTAI. Il a montré que le problème est NP-complet, par ``réduction non-déterministe''. L'évaluation de la difficulté des problèmes d'approximation liés au problème précédent a depuis pris un essor important. La difficulté intrinsèque des problèmes d'approximation dans les réseaux est une autre voie de recherche qui m'intéresse (parallèlement au point 4). Par exemple, la recherche d'une base réduite au sens de Lovász, avec la valeur optimale $1$ pour le paramètre d'approximation, est-elle NP-complet? Sur la difficulté des problèmes d'approximation dans les réseaux, j'envisage à moyen terme une collaboration avec JEAN-PIERRE SEIFERT de l'université de Francfort.