Memeriksa kesetaraan dua polytopes

14

Pertimbangkan vektor variabel $\vec{x}$ , dan seperangkat batasan linear yang ditentukan oleh $A\vec{x}\leq b$ .

Selanjutnya, pertimbangkan dua polytopes

\begin{aligned} P_{1} & = {(f_{1} (\vec{x}), \dots, f_{m} (\vec{x})) ∣ SEBUAH \vec{x} \leq b} \\ P_{2} & = {(g_{1} (\vec{x}), \dots, g_{m} (\vec{x})) ∣ SEBUAH \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*}$

di mana dan adalah pemetaan affine . Yaitu, mereka dalam bentuk . (Kami mencatat bahwa dan adalah polytopes karena mereka adalah "pemetaan affine" dari polytope .) $f$ $g$ $\vec{c}\cdot \vec{x} +d$ $P_1$ $P_2$ $A\vec{x}\leq b$

Pertanyaannya adalah, bagaimana cara memutuskan apakah dan sama dengan set? Apa kerumitannya? $P_1$ $P_2$

Motivasi masalah adalah dari jaringan sensor, tetapi tampaknya menjadi masalah geometri yang indah (mungkin dasar?). Satu dapat memecahkan ini di exptime, mungkin dengan enumerasi semua simpul dari dan , tetapi ada pendekatan yang lebih baik? $P_1$ $P_2$

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

2

Apa yang Anda maksud dengan dua polytope yang setara? Tiga interpretasi segera muncul di benak saya: sama dengan set, setara setara, dan setara kombinasi. Dua jawaban yang ada memiliki interpretasi yang berbeda.

Tsuyoshi Ito

Maksud saya sama dengan set.

maomao

Harap edit pertanyaan untuk memasukkan klarifikasi itu. Jangan tinggalkan saja di komentar. Pertanyaan harus lengkap: orang tidak harus membaca komentar untuk memahami apa yang Anda tanyakan. Terima kasih.

DW

12

Saya tidak bisa mengatakan dengan pasti apakah Anda akan menganggap pendekatan berikut ini lebih baik, tetapi dari sudut pandang kompleksitas-teoretis ada solusi yang lebih efisien. Idenya adalah untuk mengulangi pertanyaan Anda dalam teori orde pertama dari rasional dengan penambahan dan ketertiban. Anda memiliki yang termasuk dalam jika dan hanya jika $P_1$ $P_2$ berlaku. Jelaslah cara menurunkan kesetaraandandengan cara yang sama. Sekarangmemiliki awalan kuantifikasi-alternasi tetap, dan akibatnya dapat dipilih dalam, tingkat kedua dari hierarki waktu polinomial (Sontag, 1985

\begin{aligned} Φ : = \forall \vec{x} . \exists \vec{y} . (SEBUAH \cdot \vec{x} \leq b ⟹ (SEBUAH \cdot \vec{y} \leq b \land \underset{1 \leq saya \leq m}{⋀} f_{saya} (\vec{x}) = g_{saya} (\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}$ ). Saya cukup yakin bahwa mungkin juga untuk membuktikan batas bawah yang cocok, saya ingat pernah membaca di suatu tempat bahwa inklusi antara dua polytopes adalah

-hard.

Π_{2}^{P}

$\Pi_2^\text{P}$

Jika Anda mencari dukungan alat untuk menyelesaikan masalah seperti itu dalam praktiknya, pemecah SMT modern seperti z3 sepenuhnya mendukung teori ini.

Christoph Haase
sumber

5

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

Denis Pankratov
sumber

2

Saya tidak berpikir argumen ini berhasil - ia mengabaikan dimensi simpleks yang diberikan oleh teorema yang dikutip. (x adalah bagian dari input, jadi pengurangan apa pun perlu memastikan itu terikat secara polinomi)

Colin McQuillan

Poin bagus! Tampaknya klaim saya masih harus dijalani, tetapi kita harus masuk ke dalam bukti di koran yang saya kutip. Dimulai dengan grafik mereka membangun sebuah polytope, sehingga dua grafik isomorfik jika dan hanya jika polytopes yang sesuai adalah isomorfik. Polytopesnya memiliki jumlah polinomial dari simpul, dan deskripsi verteksnya dapat dihitung dalam waktu polinomial. Dengan demikian, kita dapat mengambil (A, b) menjadi simpleks dalam dimensi yaitu jumlah simpul dan f untuk menjadi proyeksi afin yang memberikan polytope yang dapat diperoleh dari deskripsi simpul.

Denis Pankratov

Memeriksa kesetaraan dua polytopes

Jawaban: