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$

cc.complexity-theory linear-algebra linear-programming polytope 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

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

Odpowiedzi: