Überprüfung der Äquivalenz zweier Polytope

14

Betrachten Sie einen Vektor von Variablen und eine Reihe linearer Bedingungen, die durch A xb spezifiziert sind .xAxb

Betrachten Sie außerdem zwei Polytope

P1={(f1(x),,fm(x))Axb}P2={(g1(x),,gm(x))Axb}

wo 's und g ' s sind affine Abbildungen. Sie haben nämlich die Form cx + d . (Wir stellen fest, dass P 1 und P 2 Polytope sind, weil sie "affine Abbildungen" des Polytops A xb sind .)fgcx+dP1P2Axb

Die Frage ist, wie zu entscheiden ist, ob und P 2 als Mengen gleich sind. Was ist die Komplexität?P1P2

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 P 2 , aber gibt es einen besseren Ansatz?P1P2

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

Antworten:

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 P 2 enthalten ist, wenn Φ : = x . y . ( A xbP1P2 gilt. Es ist klar, wie die Äquivalenz vonP1undP2auf die gleiche Weise abgeleitet werden kann. Nun hatΦein festes Präfix für die Quantifizierer-Alternation und ist folglich inΠP2, der zweiten Ebene der Polynom-Zeit-Hierarchie, entscheidbar (Sontag, 1985)

Φ:=x.y.(Axb(Ayb1imfi(x)=gi(y)))
P1P2ΦΠ2PΠ2P

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

AxbP1P2AbAb

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