Une borne optimale pour la programmation entière quasi-convexe
Français
Soient $F_1,\ldots ,F_s\in \mathbb {Z}[X_1,\ldots ,X_N]$ des polynômes quasiconvexes de degré majoré par $d\geq 2$, et $\ell $ une borne pour la longueur binaire de leurs coefficients. On montre que si le système $F_1\leq 0,\ldots ,F_s\leq 0$ admet une solution entière, alors il existe une telle solution à longueur binaire majorée par $(sd)^{cn} \ell $ (où $c$ est une constante, indépendante de $s,d,n$ et $\ell $). Le caractère simplement exponentiel de cette borne est intrinsèque au problème. On obtient aussi une borne similaire pour le problème de minimisation correspondant.