Sprawdzanie równoważności dwóch polytopów

14

Rozważmy wektor zmiennych i zestaw wiązań liniowych określonych przez . $\vec{x}$ $A\vec{x}\leq b$

Ponadto rozważ dwa polytopy

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

gdzie ' ' s są odwzorowaniami afinicznymi . Mianowicie mają one postać . (Zauważmy, że i są polytopami, ponieważ są „afinicznymi odwzorowaniami” politopu .) $f$ $g$ $\vec{c}\cdot \vec{x} +d$ $P_1$ $P_2$ $A\vec{x}\leq b$

Pytanie brzmi: jak zdecydować, czy i są równe zestawom? Jaka jest złożoność? $P_1$ $P_2$

Przyczyną problemu są sieci czujników, ale wydaje się, że jest to piękny (prawdopodobnie podstawowy?) Problem geometrii. Można to rozwiązać na przykład, wyliczając wszystkie wierzchołki i , ale czy istnieje lepsze podejście? $P_1$ $P_2$

— maomao
źródło

2

Co rozumiesz przez dwa równoważne politopy? Natychmiast przychodzą mi na myśl trzy interpretacje: równe jako zbiory, równorzędne i kombinatorycznie równoważne. Dwie istniejące odpowiedzi zakładają różne interpretacje.

— Tsuyoshi Ito

Mam na myśli równe jak zbiory.

— maomao

Edytuj pytanie, aby uwzględnić to wyjaśnienie. Nie zostawiaj tego w komentarzach. Pytania powinny być samodzielne: ludzie nie powinni czytać komentarzy, aby zrozumieć, o co pytasz. Dziękuję Ci.

— DW

12

Nie mogę powiedzieć na pewno, czy podoba Ci się następujące podejście jako lepsze, ale z teoretycznego punktu widzenia złożoności istnieje bardziej wydajne rozwiązanie. Chodzi o to, aby przeformułować swoje pytanie w teorii racjonalnych pierwszego rzędu z dodawaniem i porządkiem. Masz, że jest zawarty w wtedy i tylko wtedy, gdy $P_1$ $P_2$ jest ważne. Oczywiste jest, jak uzyskać równoważnośćiw ten sam sposób. Terazma stały przedrostek kwantyfikator-przemienność, a zatem jest rozstrzygalny w, drugim poziomie hierarchii czasu wielomianowego (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}$

Jeśli szukasz wsparcia narzędziowego w celu rozwiązania takich problemów w praktyce, nowoczesne rozwiązania SMT, takie jak Z3, w pełni obsługują tę teorię.

— Christoph Haase
źródło

5

Fakt, że leżący u podstaw polytop $Ax \le b$ jest taki sam dla $P_1$ i $P_2$ nie ma znaczenia, chyba że wiemy coś konkretnego $A$ i $b$ . Wynika to z faktu, że ogólny polytop jest afiniczną projekcją simpleksu (patrz na przykład Ziegler „Lectures for Polytopes”, Theorem 2.15). Zatem jeśli $A$ i $b$ zakoduj simplex, twoje pytanie jest równoznaczne z postawieniem pytania, jak twardy jest ogólny izomorfizm polytopów. Szybkie wyszukiwanie ujawnia następujący artykuł Kaibela i Schwartza na temat złożoności problemów związanych z izomorfizmem politopów , gdzie pokazują, że jest to trudny wykres izomorficzny.

— Denis Pankratov
źródło

2

Nie sądzę, aby ten argument działał - ignoruje on wymiar simpleks podany w cytowanym twierdzeniu. (x jest częścią danych wejściowych, więc każda redukcja musi być pewna, że jest ograniczona wielomianowo)

— Colin McQuillan

Słuszna uwaga! Wydaje się, że moje roszczenie powinno jeszcze zostać rozpatrzone, ale musimy zajrzeć do dowodu w cytowanym przeze mnie artykule. Zaczynając od wykresu, konstruują polytop, tak że dwa wykresy są izomorficzne wtedy i tylko wtedy, gdy odpowiadające im polytopy są izomorficzne. Ich polytopy mają wielomianową liczbę wierzchołków, a ich opisy wierzchołków można obliczyć w czasie wielomianowym. Zatem możemy przyjąć (A, b) za jedność w wymiarze, która jest liczbą wierzchołków if, aby być projekcją afiniczną, która daje polytop, który można uzyskać z opisu wierzchołka.

— Denis Pankratov