Vérification de l'équivalence de deux polytopes

14

Considérons un vecteur de variables et un ensemble de contraintes linéaires spécifiées par . $\vec{x}$ $A\vec{x}\leq b$

En outre, considérons deux polytopes

\begin{aligned} P_{1} & = {(f_{1} (\vec{x}), \dots, f_{m} (\vec{x})) ∣ A \vec{x} \leq b} \\ P_{2} & = {(g_{1} (\vec{x}), \dots, g_{m} (\vec{x})) ∣ A \vec{x} \leq b} \end{aligned}

$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*}$

où et sont des mappages affins. À savoir, ils sont de la forme . (Nous notons que et sont des polytopes car ce sont des "mappages affins" du polytope .) $f$ $g$ $\vec{c}\cdot \vec{x} +d$ $P_1$ $P_2$ $A\vec{x}\leq b$

La question est de savoir comment déterminer si $P_1$ et $P_2$ sont égaux en tant qu'ensembles? Quelle est la complexité?

Le problème vient des réseaux de capteurs, mais il semble que ce soit un joli problème de géométrie (probablement basique?). On peut résoudre cela en temps réel, éventuellement en énumérant tous les sommets de $P_1$ et $P_2$ , mais y a-t-il une meilleure approche?

cc.complexity-theory linear-algebra linear-programming polytope maomao
la source

2

Qu'entendez-vous par deux polytopes équivalents? Trois interprétations me viennent immédiatement à l'esprit: égales comme des ensembles, affinement équivalentes et combinatoires équivalentes. Les deux réponses existantes supposent des interprétations différentes.

Tsuyoshi Ito

Je veux dire égal comme ensembles.

maomao

Veuillez modifier la question pour inclure cette clarification. Ne vous contentez pas de le laisser dans les commentaires. Les questions doivent être autonomes: les gens ne devraient pas avoir à lire les commentaires pour comprendre ce que vous demandez. Je vous remercie.

DW

12

Je ne peux pas dire avec certitude si vous considérerez l'approche suivante comme meilleure, mais d'un point de vue théoriquement complexe, il existe une solution plus efficace. L'idée est de reformuler votre question dans la théorie du premier ordre des rationnels avec addition et ordre. Vous avez que est inclus dans si et seulement si est valide. Il est clair comment dériver l'équivalence de et de la même manière. Maintenant $P_1$ $P_2$

\begin{aligned} Φ : = \forall \vec{X} . \exists \vec{y} . (UNE \cdot \vec{X} \leq b ⟹ (UNE \cdot \vec{y} \leq b \land \underset{1 \leq je \leq m}{⋀} F_{je} (\vec{X}) = g_{je} (\vec{y}))) \end{aligned}

$\begin{align*} \Phi := \forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right) \end{align*}$

P_{1}

$P_1$

P_{2}

$P_2$

Φ

$\Phi$ a un préfixe d'alternance quantificateur fixe, et est donc décidable dans , le deuxième niveau de la hiérarchie polynomiale-temps ( Sontag, 1985 ). Je suis assez confiant qu'il est également possible de prouver une borne inférieure correspondante, je me souviens avoir lu quelque part que l'inclusion entre deux polytopes est -hard.

Π_{2}^{P}

$\Pi_2^\text{P}$

Π_{2}^{P}

$\Pi_2^\text{P}$

Si vous recherchez un support d'outils pour résoudre de tels problèmes dans la pratique, les solveurs SMT modernes tels que z3 soutiennent pleinement cette théorie.

Christoph Haase
la source

5

Le fait que le polytope sous-jacent soit le même pour et n'a pas d'importance, à moins que nous ne sachions quelque chose de spécifique sur et . Cela est dû au fait qu'un polytope général est une projection affine d'un simplex (voir, par exemple, "Lectures for Polytopes" de Ziegler, Théorème 2.15). Ainsi, si et codent pour un simplexe, votre question équivaut à demander à quel point l'isomorphisme général des polytopes est dur. Une recherche rapide révèle l'article suivant de Kaibel et Schwartz sur la complexité des problèmes d'isomorphisme polytopique , où ils montrent qu'il est dur d'isomorphisme graphique. $Ax \le b$ $P_1$ $P_2$ $A$ $b$ $A$ $b$

Denis Pankratov
la source

2

Je ne pense pas que cet argument fonctionne - il ignore la dimension du simplexe donnée par le théorème cité. (x fait partie de l'entrée, donc toute réduction doit s'assurer qu'elle est délimitée polynomialement)

Colin McQuillan

Bon point! Il semble que ma demande doive encore être menée à bien, mais nous devons entrer dans la preuve dans le document que j'ai cité. En commençant par un graphique, ils construisent un polytope, de sorte que deux graphiques sont isomorphes si et seulement si les polytopes correspondants sont isomorphes. Leurs polytopes ont un nombre polynomial de sommets, et leurs descriptions de sommets peuvent être calculées en temps polynomial. Ainsi, nous pouvons prendre (A, b) pour être un simplexe dans la dimension qui est le nombre de sommets et f pour être la projection affine qui donne le polytope qui peut être obtenu à partir de la description des sommets.

Denis Pankratov

Vérification de l'équivalence de deux polytopes

Réponses: