 |
Considérons k ensembles de points S_1,...,S_k dans Q^d. Le problème de la programmation linéaire colorée, défini par Barany et Onn (Mathematics of Operations Research, 22 (1997), 550--567), consiste à décider s'il existe un sous-ensemble T dans l'union des S_i tel que T instersecte chaque S_i au plus une fois et contient 0 dans son enveloppe convexe. Dans leur article,Barany et Onn prouvent que ce problème est NP-complet quand k=d. La complexité du cas k=d+1 est laissée en question ouverte dans ce même article. Contrairement au cas k=d ce dernier cas ne devient pas trivial quand les points sont en position générique.
Nous résolvons la question en montrant que ce cas est encore NP-complet. Nous montrons également que si P=NP, alors il existe un algorithme polynomial simple calculant un équilibre de Nash dans un jeu bimatriciel à partir de tout algorithme polynomial résolvant la programmation linéaire coloré pour le cas k=d+1, utilisé comme un sous-programme. Enfin nous proposons une adaptation de l'algorithme de Barany et Onn calculant une solution T dans un cas particulier. Cette adaptation peut être interprétée comme une "Phase I" de la méthode du simplexe.
