Dapatkah seseorang secara efisien sampel tetangga simpul dalam grafik polytope?

Saya memiliki polytope didefinisikan oleh .$P$$\{ x : Ax \leq b, x \geq 0\}$

Pertanyaan: Diberikan simpul dari , apakah ada algoritma waktu polinomial untuk sampel seragam dari tetangga dalam grafik ? (Polinomial dalam dimensi, jumlah persamaan, dan representasi . Saya dapat mengasumsikan bahwa jumlah persamaan adalah polinomial dalam dimensi.)$v$$P$$v$$P$$b$

Pembaruan: Saya pikir saya dapat menunjukkan bahwa ini NP-hard, lihat jawaban saya yang menjelaskan argumen. (Dan dengan -hard, maksud saya algoritma waktu polinomial akan membuktikan ... tidak yakin apa terminologi yang benar di sini.)$NP$$RP = NP$

Pembaruan 2: Ada bukti 2 garis -kekerasan (diberi politin kombinatorial yang tepat) dan saya dapat menemukannya artikel oleh Khachiyan. Lihat jawaban untuk deskripsi dan tautan. :-D$NP$

Masalah yang setara :

Dalam komentar-komentar Peter Shor menunjukkan bahwa pertanyaan ini setara dengan pertanyaan apakah kita dapat mengambil sampel secara seragam dari simpul-simpul sebuah polytope yang diberikan. (Saya pikir persamaannya seperti ini: Dalam satu arah, kita dapat beralih dari polytope dengan simpul ke angka simpul di , , dan mengambil sampel simpul setara dengan sampel tetangga) pada Di arah lain, kita dapat pergi dari polytope ke polytope dari satu dimensi yang lebih tinggi dengan menambahkan kerucut dengan apex dan basis Kemudian mengambil sampel tetangga$P$$v$$v$$P/v$$P/v$$v$$P$$P$$Q$$v$$P$$v$ dalam setara dengan pengambilan sampel simpul )$Q$$P$

Perumusan pertanyaan ini telah diajukan sebelumnya: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope

Sunting 2: Secara memalukan, ada dua bukti garis $NP$ -kekerasan, jika seseorang memulai dengan polytope kanan.

Pertama, ingat polytope sirkulasi grafik di bagian bawah halaman 4 dari Menghasilkan semua simpul polihedron adalah sulit .

Verteks-nya berada dalam korespondensi bijective dengan siklus sederhana yang diarahkan. Oleh karena itu, mereka sulit untuk sampel atau dihitung dengan JVV Proposition 5.1 . :-D

Dilengkapi dengan kata kunci ini, saya dapat menemukan kekerasan hasil pengambilan sampel sebagai teorema 1 dari Hypergraphs Transversal dan Keluarga Kerucut Polihedral oleh Khachiyan.

Sunting: Saya menulis argumen di bawah ini, dan tampaknya benar. Namun, ada argumen yang jauh lebih sederhana, yang akan saya uraikan di sini:

a) Dengan Analisis algoritma backtrack untuk daftar semua simpul dan semua wajah dari polyhedron cembung (Fukuda et al.) Sangat sulit untuk menyelesaikan masalah berikut pada polytopes:

Input: Polytope $Ax = b , x \geq 0$ dalam $\mathbb{R}^n$ a subset $S \subseteq n$

Output: Apakah ada simpul $v$ dari $P$ yang nol pada masing-masing koordinat di $S$ .

b) Dengan ini, kita dapat membuat konstruksi berikut: memperkenalkan variabel baru $y_{ik}$ untuk $i \in S$ dan $k = 1, \ldots, d$ , dan memperkenalkan ketidaksetaraan $0 \leq y_{ik} \leq x_i$ . Sebut polytope yang dihasilkan $P_{S,d}$ . Inti dari konstruksi ini adalah untuk memperkenalkan hypercube di atas setiap sudut, dari dimensi $d |supp(x) \cap S|$.

c) Seseorang dapat memeriksa bahwa simpul-simpul dari polytope ini semuanya terletak di atas simpul-simpul polytope lama, dan bahwa jumlah simpul di atas simpul adalah $2^{d | supp(x) \cap S|}$, Di mana $supp$ adalah fungsi yang mengirimkan vertex ke koordinat mana itu adalah nol.

d) Dengan rantai argumen tipe bigons yang biasa, maka dengan mengambil $d$ cukup besar, sampel yang seragam dari simpul $P_{S,d}$ akan (dengan probabilitas tinggi) memberikan sampel dari simpul yang memaksimalkan ukuran persimpangan mereka dengan $S$ .

Tampaknya ada berbagai ekstensi ini. Saya akan memperbarui dengan tautan ketika penulisan selesai.

(Argumen lama dulu ada di sini - itu ada dalam sejarah edit. Saya sudah menghapusnya karena sangat panjang dan akan mengganggu menemukan jawaban yang benar untuk pertanyaan itu.)