Überprüfung der Äquivalenz zweier Polytope

14

Betrachten Sie einen Vektor von Variablen und eine Reihe linearer Bedingungen, die durch spezifiziert sind . $\vec{x}$ $A\vec{x}\leq b$

Betrachten Sie außerdem zwei Polytope

\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*}$

wo 's und ' s sind affine Abbildungen. Sie haben nämlich die Form . (Wir stellen fest, dass und Polytope sind, weil sie "affine Abbildungen" des Polytops .) $f$ $g$ $\vec{c}\cdot \vec{x} +d$ $P_1$ $P_2$ $A\vec{x}\leq b$

Die Frage ist, wie zu entscheiden ist, ob und als Mengen gleich sind. Was ist die Komplexität? $P_1$ $P_2$

Die Motivation des Problems liegt in Sensornetzwerken, aber es scheint ein schönes (wahrscheinlich grundlegendes?) Geometrieproblem zu sein. Man kann dies in Exeptime lösen, möglicherweise durch Aufzählen aller Eckpunkte von und , aber gibt es einen besseren Ansatz? $P_1$ $P_2$

cc.complexity-theory linear-algebra linear-programming polytope maomao
quelle

2

Was meinen Sie damit, dass zwei Polytope gleichwertig sind? Mir fallen sofort drei Interpretationen ein: Gleich wie Mengen, affin äquivalent und kombinatorisch äquivalent. Die beiden vorhandenen Antworten werden unterschiedlich interpretiert.

Tsuyoshi Ito

Ich meine gleich wie sätze.

Maomao

Bitte bearbeiten Sie die Frage, um diese Klarstellung aufzunehmen. Lass es nicht einfach in den Kommentaren. Fragen sollten in sich geschlossen sein: Die Leute sollten die Kommentare nicht lesen müssen, um zu verstehen, was Sie fragen. Vielen Dank.

DW

12

Ich kann nicht sicher sagen, ob Sie den folgenden Ansatz für besser halten, aber aus komplexitätstheoretischer Sicht gibt es eine effizientere Lösung. Die Idee ist, Ihre Frage in der Theorie erster Ordnung der Rationals mit Addition und Ordnung umzudrücken. Sie haben, dass genau dann in ist, wenn $P_1$ $P_2$ gilt. Es ist klar, wie die Äquivalenz vonundauf die gleiche Weise abgeleitet werden kann. Nun hatein festes Präfix für die Quantifizierer-Alternation und ist folglich in, der zweiten Ebene der Polynom-Zeit-Hierarchie, entscheidbar (Sontag, 1985)

\begin{aligned} Φ := \forall \vec{x} . \exists \vec{y} . (A \cdot \vec{x} \leq b ⟹ (A \cdot \vec{y} \leq b \land \underset{1 \leq i \leq m}{⋀} f_{i} (\vec{x}) = g_{i} (\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$

Π_{2}^{P}

$\Pi_2^\text{P}$

Π_{2}^{P}

$\Pi_2^\text{P}$

Wenn Sie nach Werkzeugunterstützung suchen, um solche Probleme in der Praxis zu lösen, unterstützen moderne SMT-Löser wie z3 diese Theorie voll und ganz.

Christoph Haase
quelle

5

$Ax \le b$ $P_1$ $P_2$ $A$ $b$ $A$ $b$

Denis Pankratov
quelle

2

Ich denke nicht, dass dieses Argument funktioniert - es ignoriert die Dimension des Simplex, die durch den zitierten Satz gegeben ist. (x ist Teil der Eingabe, daher muss jede Reduzierung sicherstellen, dass sie polynomiell begrenzt ist)

Colin McQuillan

Guter Punkt! Es scheint, dass meine Behauptung noch durchgehen sollte, aber wir müssen in den von mir zitierten Beweis in der Zeitung gehen. Ausgehend von einem Graphen konstruieren sie ein Polytop, sodass zwei Graphen genau dann isomorph sind, wenn die entsprechenden Polytope isomorph sind. Ihre Polytope haben eine polynomielle Anzahl von Scheitelpunkten, und ihre Scheitelpunktbeschreibungen können in Polynomzeit berechnet werden. Wir können also annehmen, dass (A, b) ein Simplex in der Dimension ist, die der Anzahl der Scheitelpunkte entspricht, und dass f die affine Projektion ist, die das Polytop ergibt, das aus der Scheitelpunktbeschreibung erhalten werden kann.

Denis Pankratov

Überprüfung der Äquivalenz zweier Polytope

Antworten: