Czy można skutecznie i równomiernie próbkować sąsiada wierzchołka na wykresie polytopa?

Mam politotop $P$ zdefiniowany przez $\{ x : Ax \leq b, x \geq 0\}$ .

Pytanie: Z uwagi wierzchołek $v$ z $P$ , czy istnieje algorytm wielomianowy czas równomiernie próbki od sąsiadów $v$ na wykresie $P$ ? (Wielomian w wymiarze, liczba równań i reprezentacja $b$ . Mogę założyć, że liczba równań jest wielomianem w wymiarze).

Aktualizacja: Wydaje mi się, że byłem w stanie wykazać, że jest to trudny NP, patrz moja odpowiedź wyjaśniająca ten argument. (I przez $NP$ -hard, to znaczy, że algorytm czas wielomian okaże $RP = NP$ ... nie jestem pewien co poprawna terminologia jest tutaj).

Aktualizacja 2: Jest to dowód 2 linia $NP$ -hardness (biorąc pod uwagę prawo kombinatoryczne Polytope) i udało mi się go znaleźć artykuł Khachiyan. Zobacz odpowiedź na opis i link. :-RE

Równoważny problem :

W komentarzach Peter Shor wskazał, że pytanie to jest równoważne z pytaniem, czy możemy równomiernie próbkować z wierzchołków danego polytopa. (Myślę, że równoważność wygląda następująco: w jednym kierunku możemy przejść od politopu $P$ z wierzchołkiem $v$ do liczby wierzchołków w $v$ , $P/v$ , a próbkowanie wierzchołków $P/v$ jest równoważne próbkowaniu sąsiadów $v$ na $P$ W drugim kierunku możemy przejść od polytopa $P$ do polytopa $Q$ jednego wyższego wymiaru, dodając stożek z wierzchołkiem $v$ i podstawą $P$. Następnie próbkowanie sąsiadów $v$ w $Q$ jest równoważne próbkowaniu wierzchołków $P$ ).

Takie sformułowanie pytania zostało zadane wcześniej: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope

$NP$

Najpierw przypomnij sobie o wielobiegunowym obiegu wykresu na dole strony 4 Generowanie wszystkich wierzchołków wielościanu jest trudne .

Jego wierzchołki są bijectywnie zgodne z ukierunkowanymi prostymi cyklami. Dlatego trudno je próbkować lub liczyć według Propozycji 5.1 JVV . :-RE

Wyposażony w te słowa kluczowe byłem w stanie znaleźć twardość wyniku próbkowania jako twierdzenie 1 Transversal Hypergraphs and Families of Polyhedes Cones autorstwa Khachiyana.

Edycja: Zapisałem poniższy argument i wydaje się poprawny. Istnieje jednak znacznie prostszy argument, który opiszę tutaj:

a) Analiza algorytmów cofania do wyliczenia wszystkich wierzchołków i wszystkich powierzchni wypukłego wielościanu (Fukuda i in.) jest bardzo trudna do rozwiązania w NP:

$Ax = b , x \geq 0$$\mathbb{R}^n$$S \subseteq n$

$v$$P$$S$

$y_{ik}$$i \in S$$k = 1, \ldots, d$$0 \leq y_{ik} \leq x_i$$P_{S,d}$$d |supp(x) \cap S|$

$2^{d | supp(x) \cap S|}$$supp$

$d$$P_{S,d}$$S$

Wydaje się, że istnieją różne rozszerzenia tego. Po zakończeniu pisania zaktualizuję link.

(Stary argument był tutaj - jest w historii edycji. Usunąłem go, ponieważ jest bardzo długi i będzie przeszkadzał w znalezieniu prawidłowej odpowiedzi na pytanie.)